1 #include <cstdio>  2 #include <cstring>  3 #include <cstdlib>  4   5 #define MAXN 1005  6 #define INF 0xfffff  7 #define MAXM 27  8   9 int wa[MAXN], wb[MAXN], ws[MAXN], wv[MAXN]; 10 char s[MAXN]; 11 int str[MAXN], sa[MAXN]; 12 int height[MAXN], rank[MAXN]; 13  14 int max(int a, int b) { 15     return a>b ? a:b; 16 } 17  18 int min(int a, int b) { 19     return a<b ? a:b; 20 } 21  22 int cmp(int *r, int a, int b, int l) { 23     return r[a]==r[b] && r[a+l]==r[b+l]; 24 } 25  26 void da(int *r, int *sa, int n, int m) { 27     int i, j, *x = wa, *y = wb, *t; 28     int p; 29  30     for (i=0; i<m; ++i) ws[i] = 0; 31     for (i=0; i<n; ++i) ws[x[i]=r[i]]++; 32     for (i=1; i<m; ++i) ws[i] += ws[i-1]; 33     for (i=n-1; i>=0; --i) sa[--ws[x[i]]] = i; 34     for (j=1, p=1; j<n; j*=2, m=p) { 35         for (p=0, i=n-j; i<n; ++i) y[p++] = i; 36         for (i=0; i<n; ++i) if (sa[i] >= j) y[p++] = sa[i] - j; 37         for (i=0; i<n; ++i) wv[i] = x[y[i]]; 38         for (i=0; i<m; ++i) ws[i] = 0; 39         for (i=0; i<n; ++i) ws[wv[i]]++; 40         for (i=1; i<m; ++i) ws[i] += ws[i-1]; 41         for (i=n-1; i>=0; --i) sa[--ws[wv[i]]] = y[i]; 42         for (t=x, x=y, y=t, p=1, x[sa[0]]=0, i=1; i<n; ++i) 43             x[sa[i]] = cmp(y, sa[i-1], sa[i], j) ? p-1 : p++; 44     } 45 } 46  47 void calheight(int *r, int *sa, int n) { 48     int i, j, k = 0; 49  50     for (i=1; i<=n; ++i) rank[sa[i]] = i; 51     for (i=0; i<n; height[rank[i++]]=k) 52         for (k? --k:0, j=sa[rank[i]-1]; r[i+k]==r[j+k]; ++k) 53             /*do nothing*/; 54 } 55  56 int getRepeat(int len, int n) { 57     int i, maxx, minn; 58     int ret = 0; 59  60     maxx = -1; 61     minn = INF; 62  63     for (i=1; i<=n; ++i) { 64         if (height[i] >= len) { 65             maxx = max(sa[i], max(sa[i-1], maxx)); 66             minn = min(sa[i], min(sa[i-1], minn)); 67         } else { 68             if (maxx!=-1 && minn!=INF && (maxx-minn)>=len) 69                 ++ret; 70             maxx = -1; 71             minn = INF; 72         } 73     } 74  75     if (maxx!=-1 && minn!=INF && (maxx-minn)>=len) 76         ++ret; 77  78     return ret; 79 } 80  81 void printRank(int n) { 82     int i; 83  84     printf("print rank...\n"); 85     for (i=1; i<=n; ++i) 86         printf("%d ", rank[i]); 87     printf("\n"); 88 } 89  90 void printHeight(int n) { 91     int i; 92  93     printf("print height...\n"); 94     for (i=1; i<=n; ++i) 95         printf("%d ", height[i]); 96     printf("\n"); 97 } 98  99 void printSa(int n) {100     int i;101 102     printf("print sa...\n");103     for (i=0; i<=n; ++i)104         printf("%d ", sa[i]);105     printf("\n");106 }107 108 int main() {109     int i, len;110     int ans;111 112 #ifndef ONLINE_JUDGE113     freopen("data.in", "r", stdin);114     freopen("data.out", "w", stdout);115 #endif116 117     while (scanf("%s",s)!=EOF && (s[0]!=‘#‘)) {118         //printf("%s\n", s);119         for (i=0; s[i]; ++i)120             str[i] = s[i] - ‘a‘ + 1;121         str[i] = 0;122         len = i;123         da(str, sa, len+1, MAXM);124         calheight(str, sa, len);125 #ifndef ONLINE_JUDGE126         printSa(len);127         printRank(len);128         printHeight(len);129 #endif130         for (ans=0, i=1; i<=len/2; ++i) {131             ans += getRepeat(i, len);132         }133         printf("%d\n", ans);134     }135 136     return 0;137 }