0001 void buildGS(char* P, int m, int* gs) { //O(m = |P|)
0002    int* ss = new int[m];  buildSS(P, m, ss); //先构造SS表，以下再构造GS表
0003    for (int j = 0; j < m; j++) gs[j] = m; //初始化
0004    for (int i = 0, j = m-1, d = 0; 0 <= j; j--, d++) //自后向前检视各项ss[j]（始终记d=m-1-j）
0005       if (j+1 == ss[j]) //若P[0,j] = P[d,m-1]，则对于每个i<d，d都是gs[i]的一种选择
0006          while (i < d) //所有的while循环均由i控制，而i全程从0到m-1单调递增，故累计仅O(m)
0007             gs[i++] = d; //d单调递增，故各项的首次赋值即是最小者
0008    for (int j = 0, d = m-1; j < m-1; j++, d--) //每一项ss[j]，都是gs[m-1-ss[j]]的一种选择
0009       gs[m-1-ss[j]] = d; //自前向后遍历，d单调递减，故各项最终都会保留最小者（画家算法）
0010    delete[] ss;
0011 } //buildGS