0001 int* buildSS ( char* P ) { //构造最大匹配后缀长度表：O(m)
0002    int m = strlen ( P ); int* ss = new int[m]; //Suffix Size表
0003    ss[m - 1]  =  m; //对最后一个字符而言，与之匹配的最长后缀就是整个P串
0004 // 以下，从倒数第二个字符起自右向左扫描P，依次计算出ss[]其余各项
0005    for ( int lo = m - 1, hi = m - 1, j = lo - 1; j >= 0; j -- )
0006       if ( ( lo < j ) && ( ss[m - hi + j - 1] < j - lo ) ) //情况一
0007          ss[j] =  ss[m - hi + j - 1]; //直接利用此前已计算出的ss[]
0008       else { //情况二
0009          hi = j; lo = min ( lo, hi );
0010          while ( ( 0 <= lo ) && ( P[lo] == P[m - hi + lo - 1] ) ) //二重循环？
0011             lo--; //逐个对比处于(lo, hi]前端的字符
0012          ss[j] = hi - lo;
0013       }
0014    return ss;
0015 }
0016 
0017 int* buildGS ( char* P ) { //构造好后缀位移量表：O(m)
0018    int* ss = buildSS ( P ); //Suffix Size table
0019    size_t m = strlen ( P ); int* gs = new int[m]; //Good Suffix shift table
0020    for ( size_t j = 0; j < m; j ++ ) gs[j] = m; //初始化
0021    for ( size_t i = 0, j = m - 1; j < UINT_MAX; j-- ) //逆向逐一扫描各字符P[j]
0022       if ( j + 1 == ss[j] ) //若P[0, j] = P[m - j - 1, m)，则
0023          while ( i < m - j - 1 ) //对于P[m - j - 1]左侧的每个字符P[i]而言（二重循环？）
0024             gs[i++] = m - j - 1; //m - j - 1都是gs[i]的一种选择
0025    for ( size_t j = 0; j < m - 1; j ++ ) //画家算法：正向扫描P[]各字符，gs[j]不断递减，直至最小
0026       gs[m - ss[j] - 1] = m - j - 1; //m - j - 1必是其gs[m - ss[j] - 1]值的一种选择
0027    delete [] ss; return gs;
0028 }