//1403
思路：字符串的任何一个子串都是这个字符串的某个后缀的前缀，则求A和B的最长公共子串等价于求A的后缀和B的后缀的最长公共前缀的最大值。
做法：将第二个字符串写在第一个字符串后面，中间用一个没有出现过的字符隔开，再求这个新的字符串的后缀数组。
1 #include "bits/stdc++.h" 2 using namespace std; 3 const int maxn = 1e6 + 10; 4 char str[maxn]; 5 int int_str[maxn]; 6 int len; 7 int str_rank[maxn], s_r[maxn], rank_str[maxn], a[maxn], b[maxn], h_rank[maxn]; 8 9 int Count[maxn]; 10 void radix(int *str, int *s_r, int *str_rank, int len, int m) 11 { 12 int i; 13 memset(Count, 0, sizeof(Count)); 14 for(i = 0; i < len; ++i) 15 ++Count[str[s_r[i]]]; 16 for(i = 1; i <= m; ++i) 17 Count[i] += Count[i - 1]; 18 for(i = len - 1; i >= 0; --i) { 19 str_rank[--Count[str[s_r[i]]]] = s_r[i]; 20 } 21 } 22 23 void suffix_array(int *str, int *str_rank, int len, int m) 24 { 25 int i; 26 for(i = 0; i < len; ++i) 27 s_r[i] = i; 28 radix(str, s_r, str_rank, len, m); 29 rank_str[str_rank[0]] = 0; 30 for(i = 1; i < len; ++i) { 31 rank_str[str_rank[i]] = rank_str[str_rank[i - 1]] + (str[str_rank[i - 1]] != str[str_rank[i]]); 32 } 33 int j; 34 for(i = 0; (1 << i) < len; ++i) { 35 for(j = 0; j < len; ++j) { 36 a[j] = rank_str[j] + 1; 37 b[j] = ((1 << i) + j < len)? rank_str[(1 << i) + j] + 1: 0; 38 str_rank[j] = j; 39 } 40 radix(b, str_rank, s_r, len, len); 41 radix(a, s_r, str_rank, len, len); 42 rank_str[str_rank[0]] = 0; 43 for(j = 1; j < len; ++j) { 44 rank_str[str_rank[j]] = rank_str[str_rank[j - 1]] + (a[str_rank[j - 1]] != a[str_rank[j]] || b[str_rank[j - 1]] != b[str_rank[j]]); 45 } 46 } 47 } 48 49 void cal_h(int *str, int *str_rank, int *h_rank, int len) 50 { 51 int i, k = 0; 52 for(i = 0; i < len; ++i) { 53 rank_str[str_rank[i]] = i; 54 } 55 for(i = 0; i < len; ++i) { 56 k = (k == 0? 0: k - 1); 57 if(rank_str[i] != 0) { 58 while(str[i + k] == str[str_rank[rank_str[i] - 1] + k]) 59 ++k; 60 } 61 h_rank[rank_str[i]] = k; 62 } 63 } 64 65 66 int main() 67 { 68 while(scanf("%s", str) != EOF) { 69 len = strlen(str); 70 int len1 = len; 71 str[len] = 'a' - 1; 72 scanf("%s", str + len + 1); 73 len = strlen(str); 74 int i; 75 for(i = 0; i < len; ++i) 76 int_str[i] = str[i]; 77 suffix_array(int_str, str_rank, len, 200); 78 cal_h(int_str, str_rank, h_rank, len); 79 80 // for(i = 0; i < len; ++i) { 81 // printf("%d: %s %d ", i + 1, str + str_rank[i], h_rank[i]); 82 // } 83 84 int res = 0; 85 for(i = 1; i < len; ++i) { 86 if(res < h_rank[i] && ((str_rank[i] < len1 && str_rank[i - 1] > len1) || (str_rank[i] > len1 && str_rank[i - 1] < len1))) 87 res = h_rank[i]; 88 } 89 printf("%d ", res); 90 } 91 92 }