0001 //***************************************************************************************** 0002 // 0 bc['X'] m-1 0003 // | | | 0004 // ........................X*************************************** 0005 // .|<------------- 'X' free ------------>| 0006 //***************************************************************************************** 0007 int* buildBC ( char* P ) { //构造Bad Charactor Shift表:O(m + 256) 0008 int* bc = new int[256]; //BC表,与字符表等长 0009 for ( size_t j = 0; j < 256; j ++ ) bc[j] = -1; //初始化:首先假设所有字符均未在P中出现 0010 for ( size_t m = strlen ( P ), j = 0; j < m; j ++ ) //自左向右扫描模式串P 0011 bc[ P[j] ] = j; //将字符P[j]的BC项更新为j(单调递增)——画家算法 0012 return bc; 0013 }