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 }