1 #include<iostream> 2 #include<stdio.h> 3 #include<string.h> 4 using namespace std; 5 #define min(x,y) x>y? y:x 6 #define N 200010 7 int dp[N][33]; 8 int wa[N], wb[N], wsf[N], wv[N], sa[N]; 9 int ra[N], height[N], s[N]; 10 char str[N], str1[N]; 11 int cmp(int *r, int a, int b, int k) 12 { 13 return r[a] == r[b] && r[a + k] == r[b + k]; 14 } 15 void getsa(int *r, int *sa, int n, int m) 16 { 17 int i, j, p, *x = wa, *y = wb, *t; 18 for (i = 0; i < m; i++) wsf[i] = 0; 19 for (i = 0; i < n; i++) wsf[x[i] = r[i]]++; 20 for (i = 1; i < m; i++) wsf[i] += wsf[i - 1]; 21 for (i = n - 1; i >= 0; i--) sa[--wsf[x[i]]] = i; 22 p = 1; 23 j = 1; 24 for (; p < n; j *= 2, m = p) 25 { 26 for (p = 0, i = n - j; i < n; i++) y[p++] = i; 27 for (i = 0; i < n; i++) if (sa[i] >= j) y[p++] = sa[i] - j; 28 for (i = 0; i < n; i++) wv[i] = x[y[i]]; 29 for (i = 0; i < m; i++) wsf[i] = 0; 30 for (i = 0; i < n; i++) wsf[wv[i]]++; 31 for (i = 1; i < m; i++) wsf[i] += wsf[i - 1]; 32 for (i = n - 1; i >= 0; i--) sa[--wsf[wv[i]]] = y[i]; 33 t = x; 34 x = y; 35 y = t; 36 x[sa[0]] = 0; 37 for (p = 1, i = 1; i < n; i++) 38 x[sa[i]] = cmp(y, sa[i - 1], sa[i], j) ? p - 1 : p++; 39 } 40 } 41 void getheight(int *r, int n) 42 { 43 int i, j, k = 0; 44 for (i = 1; i <= n; i++) ra[sa[i]] = i; 45 for (i = 0; i < n; i++) 46 { 47 if (k) 48 k--; 49 else 50 k = 0; 51 j = sa[ra[i] - 1]; 52 while (r[i + k] == r[j + k]) 53 k++; 54 height[ra[i]] = k; 55 } 56 } 57 int main() 58 { 59 while (cin >> str) 60 { 61 cin >> str1; 62 int n = 0, len = strlen(str); 63 for (int i = 0; i < len; i++) 64 s[n++] = str[i] - 'a' + 1; 65 s[n++] = 28; 66 len = strlen(str1); 67 for (int i = 0; i < len; i++) 68 s[n++] = str1[i] - 'a' + 1; 69 s[n] = 0; 70 getsa(s, sa, n + 1, 30); 71 getheight(s, n); 72 int max = 0, pos = 0; 73 len = strlen(str); 74 for (int i = 2; i<n; i++) 75 if (height[i]>max) 76 { 77 if (0 <= sa[i - 1] && sa[i - 1] < len&&len < sa[i]) 78 max = height[i]; 79 if (0 <= sa[i] && sa[i] < len&&len < sa[i - 1]) 80 max = height[i]; 81 } 82 cout << max << endl; 83 } 84 return 0; 85 }