//

思路：字符串的任何一个子串都是这个字符串的某个后缀的前缀，则求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\n", 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\n", res);90     }91 92 }