1 #include <algorithm> 2 #include <stdio.h> 3 #include <string.h> 4 #define N 100 5 char s[N+1]; 6 int n, sa[N], rank[N], height[N]; 7 namespace SABuilder { 8     int cnt[N], t1[N<<1], t2[N<<1]; 9     void work() {10         int i, k, m = 26, p, *x = t1, *y = t2;11         memset(cnt, 0, m * sizeof(int));12         for(i = 0; i < n; ++i) ++cnt[x[i] = s[i] - ‘a‘];13         for(i = 1; i < m; ++i) cnt[i] += cnt[i-1];14         for(i = n - 1; i >= 0; --i) sa[--cnt[x[i]]] = i;15         for(k = 1; k <= n; k <<= 1) {16             for(i = n-k, p = 0; i < n; ++i) y[p++] = i;17             for(i = 0; i < n; ++i) if(sa[i] >= k) y[p++] = sa[i] - k;18             memset(cnt, 0, m * sizeof(int));19             for(i = 0; i < n; ++i) ++cnt[x[y[i]]];20             for(i = 1; i < m; ++i) cnt[i] += cnt[i-1];21             for(i = n - 1; i >= 0; --i) sa[--cnt[x[y[i]]]] = y[i];22             std::swap(x, y);23             x[sa[0]] = 0;24             for(i = m = 1; i < n; ++i) {25                 x[sa[i]] = y[sa[i]]==y[sa[i-1]]&&sa[i]+k<n&&sa[i-1]+k<n&&y[sa[i]+k]==y[sa[i-1]+k] ? m-1 : m++;26             }27             if(m > n) break;28         }29         memcpy(rank, x, n * sizeof(int));30         for(i = 0, p = 0; i < n; ++i) if(rank[i]) {31             if(p) --p;32             k = sa[rank[i]-1];33             while(s[i+p] == s[k+p]) ++p;34             height[rank[i]] = p;35         }36     }37 }38 int main() {39     register int i, ans = 0;40     gets(s);41     n = strlen(s);42     SABuilder::work();43     printf("%d", ans);44     return 0;45 }