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 }