1 #include <cstdio>  2 #include <cstring>  3 #include <cstdlib>  4   5 #define MAXM 28  6 #define MAXN 100010  7   8 int wa[MAXN*2];  9 int wb[MAXN*2]; 10 int wv[MAXN*2]; 11 int ws[MAXN*2]; 12 char s[MAXN]; 13 int str[MAXN*2], sa[MAXN*2]; 14 int height[MAXN*2], rank[MAXN*2]; 15  16 bool cmp(int *r, int a, int b, int l) { 17     return r[a]==r[b] && r[a+l]==r[b+l]; 18 } 19  20 void da(int *r, int *sa, int n, int m) { 21     int i, j, *x = wa, *y = wb, *t; 22     int p; 23      24     for (i=0; i<m; ++i) ws[i] = 0; 25     for (i=0; i<n; ++i) ws[x[i]=r[i]]++; 26     for (i=1; i<m; ++i) ws[i] += ws[i-1]; 27     for (i=n-1; i>=0; --i) sa[--ws[x[i]]] = i; 28     for (j=1, p=1; j<n; j*=2, m=p) { 29         for (p=0, i=n-j; i<n; ++i) y[p++] = i; 30         for (i=0; i<n; ++i) if (sa[i] >= j) y[p++] = sa[i] - j; 31         for (i=0; i<n; ++i) wv[i] = x[y[i]]; 32         for (i=0; i<m; ++i) ws[i] = 0; 33         for (i=0; i<n; ++i) ws[wv[i]]++; 34         for (i=1; i<m; ++i) ws[i] += ws[i-1]; 35         for (i=n-1; i>=0; --i) sa[--ws[wv[i]]] = y[i]; 36         for (t=x, x=y, y=t, p=1, x[sa[0]]=0, i=1; i<n; ++i) 37             x[sa[i]] = cmp(y, sa[i-1], sa[i], j) ? p-1:p++; 38     } 39 } 40  41 void calheight(int *r, int *sa, int n) { 42     int i, j, k=0; 43      44     for (i=1; i<=n; ++i) rank[sa[i]] = i; 45     for (i=0; i<n; height[rank[i++]]=k) 46         for (k?k--:0, j=sa[rank[i]-1]; r[i+k]==r[j+k]; ++k) 47             /*do nothing*/; 48 } 49  50 void printRank(int n) { 51     int i; 52      53     printf("\nprint rank...\n"); 54     for (i=0; i<n; ++i) 55         printf("%d ", rank[i]); 56     printf("\n"); 57 } 58  59 void printSa(int n) { 60     int i; 61      62     printf("\nprint sa...\n"); 63     for (i=0; i<n; ++i) 64         printf("%d ", sa[i]); 65     printf("\n"); 66 } 67  68 void printHeight(int n) { 69     int i; 70      71     printf("\nprint height...\n"); 72     for (i=0; i<n; ++i) 73         printf("%d ", height[i]); 74     printf("\n"); 75 } 76  77 int main() { 78     int l1, l2, l; 79     int i, j, k; 80     int ans; 81      82 #ifndef ONLINE_JUDGE 83     freopen("data.in", "r", stdin); 84 #endif 85  86     while (scanf("%s", s) != EOF) { 87         l = 0; 88         for (l1=0; s[l1]; l1++) 89             str[l++] = s[l1] - ‘a‘ + 2; 90         str[l++] = 1;    // split two strings 91         scanf("%s", s); 92         for (l2=0; s[l2]; l2++) 93             str[l++] = s[l2] - ‘a‘ + 2; 94         str[l] = 0; 95         da(str, sa, l+1, MAXM); 96         calheight(str, sa, l); 97     #ifndef ONLINE_JUDGE 98         printRank(l+1); 99         printSa(l+1);100         printHeight(l);101     #endif102         ans = -1;103         for (i=2; i<=l; ++i) {104             if (height[i] > ans) {105                 if ((sa[i-1]<l1 && sa[i]>l1) || (sa[i-1]>l1 && sa[i]<l1))106                     ans = height[i];107             }108         }109         printf("%d\n", ans);110     }111 112 113     return 0;114 }