| 46 | int classesNum; |
| 47 | |
| 48 | void buildSuffixArray(string s) { |
| 49 | int n=s.size(); |
| 50 | n++; |
| 51 | for (int i = 0;i < ALPH;i++) |
| 52 | num[i] = 0; |
| 53 | for (int i = 0; i < n; i++) |
| 54 | num[s[i]]++; |
| 55 | |
| 56 | for (int i = 1; i < ALPH; i++) |
| 57 | num[i] += num[i - 1]; |
| 58 | |
| 59 | for (int i = 0; i < n; i++) { |
| 60 | p[num[s[i]] - 1] = i; |
| 61 | num[s[i]]--; |
| 62 | } |
| 63 | |
| 64 | c[p[0]][0] = 1; |
| 65 | classesNum = 1; |
| 66 | for (int i = 1; i < n; i++) { |
| 67 | if (s[p[i]] != s[p[i - 1]]) |
| 68 | classesNum++; |
| 69 | c[p[i]][0] = classesNum; |
| 70 | } |
| 71 | |
| 72 | for (int i = 1; ; i++) { |
| 73 | |
| 74 | int half = (1 << (i - 1)); |
| 75 | |
| 76 | for (int j = 0; j < n; j++) { |
| 77 | pcur[j] = p[j] - half; |
| 78 | if (pcur[j] < 0) |
| 79 | pcur[j] += n; |
| 80 | } |
| 81 | |
| 82 | for (int j = 1; j <= classesNum; j++) |
| 83 | num[j] = 0; |
| 84 | |
| 85 | for (int j = 0; j < n; j++) |
| 86 | num[c[pcur[j]][i - 1]]++; |
| 87 | for (int j = 2; j <= classesNum; j++) |
| 88 | num[j] += num[j - 1]; |
| 89 | |
| 90 | for (int j = n - 1; j >= 0; j--) { |
| 91 | p[num[c[pcur[j]][i - 1]] - 1] = pcur[j]; |
| 92 | num[c[pcur[j]][i - 1]]--; |
| 93 | } |
| 94 | |
| 95 | c[p[0]][i] = 1; |
| 96 | classesNum = 1; |
| 97 | |
| 98 | for (int j = 1; j < n; j++) { |
| 99 | int p1 = (p[j] + half) % n, p2 = (p[j - 1] + half) % n; |
| 100 | if (c[p[j]][i - 1] != c[p[j - 1]][i - 1] || c[p1][i - 1] != c[p2][i - 1]) |
| 101 | classesNum++; |
| 102 | c[p[j]][i] = classesNum; |
| 103 | } |
| 104 | |
| 105 | if ((1 << i) >= n) |