Problem Description Given two strings, you have to tell the length of the Longest Common Substring of them.
For example: str1 = banana str2 = cianaic
So the Longest Common Substring is “ana”, and the length is 3.
Input The input contains several test cases. Each test case contains two strings, each string will have at most 100000 characters. All the characters are in lower-case.
Process to the end of file.
Output For each test case, you have to tell the length of the Longest Common Substring of them.
Sample Input
banana cianaic
Sample Output
3
Author Ignatius.L
Recommend We have carefully selected several similar problems for you: 1404 1418 1422 1509 1409
Statistic | Submit | Discuss | Note
把2个字符串接在一起然后求后缀数组，，求出一个height[i]的最大值，且这2个后缀在2个字符串里
/*************************************************************************> File Name: hdu1403.cpp> Author: ALex> Mail: zchao1995@gmail.com> Created Time: 2015年04月09日 星期四 14时30分20秒 ************************************************************************/;const double pi = acos(-1.0);const int inf = 0x3f3f3f3f;const double eps = 1e-15;LL;typedef pair <int, int> PLL;int pos[220000];class SuffixArray{public:N = 220000;int init[N];int X[N];int Y[N];int Rank[N];int sa[N];int height[N];int buc[N];int LOG[N];int dp[N][20];int size;void clear(){size = 0;}void insert(int n){init[size++] = n;}bool cmp(int *r, int a, int b, int l){return (r[a] == r[b] && r[a + l] == r[b + l]);}void getsa(int m = 256) //m一般为最大值+1{init[size] = 0;int l, p, *x = X, *y = Y, n = size + 1;for (int i = 0; i < m; ++i){buc[i] = 0;}for (int i = 0; i < n; ++i){++buc[x[i] = init[i]];}for (int i = 1; i < m; ++i){buc[i] += buc[i – 1];}for (int i = n – 1; i >= 0; –i){sa[–buc[x[i]]] = i;}for (l = 1, p = 1; l <= n && p < n; m = p, l *= 2){p = 0;for (int i = n – l; i < n; ++i){y[p++] = i;}for (int i = 0; i < n; ++i){if (sa[i] >= l){y[p++] = sa[i] – l;}}for (int i = 0; i < m; ++i){buc[i] = 0;}for (int i = 0; i < n; ++i){++buc[x[y[i]]];}for (int i = 1; i < m; ++i){buc[i] += buc[i – 1];}for (int i = n – 1; i >= 0; –i){sa[–buc[x[y[i]]]] = y[i];}int i;for (swap(x, y), x[sa[0]] = 0, p = 1, i = 1; i < n; ++i){x[sa[i]] = cmp(y, sa[i – 1], sa[i], l) ? p – 1 : p++;}}}void getheight(){int h = 0, n = size;for (int i = 0; i <= n; ++i){Rank[sa[i]] = i;}height[0] = 0;for (int i = 0; i < n; ++i){if (h > 0){–h;}int j =sa[Rank[i] – 1];for (; i + h < n && j + h < n && init[i + h] == init[j + h]; ++h);height[Rank[i] – 1] = h;}}//预处理每一个数字的对数，用于rmq，常数优化void initLOG(){LOG[0] = -1;for (int i = 1; i < N; ++i){LOG[i] = (i & (i – 1)) ? LOG[i – 1] : LOG[i – 1] + 1;}}void initRMQ(){initLOG();int n = size;int limit;for (int i = 0; i < n; ++i){dp[i][0] = height[i];}for (int j = 1; j <= LOG[n]; ++j){limit = (n – (1 << j));for (int i = 0; i <= limit; ++i){dp[i][j] = min(dp[i][j – 1], dp[i + (1 << (j – 1))][j – 1]);}}}int LCP(int a, int b){int t;a = Rank[a];b = Rank[b];if (a > b){swap(a, b);}–b;t = LOG[b – a + 1];return min(dp[a][t], dp[b – (1 << t) + 1][t]);}void solve(){int ans = 0;for (int i = 1; i < size; ++i){if (pos[sa[i]] == 1 && pos[sa[i + 1]] == 2){if (ans < height[i]){ans = height[i];}}else if (pos[sa[i]] == 2 && pos[sa[i + 1]] == 1){if (ans < height[i]){ans = height[i];}}}printf(“%d\n”, ans);}}SA;char str[100110];int main(){while (~scanf(“%s”, str)){SA.clear();int cnt = 0;int len = strlen(str);for (int i = 0; i < len; ++i){SA.insert(str[i] – ‘a’ + 1);pos[cnt++] = 1;}pos[cnt++] = 0;SA.insert(27);scanf(“%s”, str);len = strlen(str);for (int i = 0; i < len; ++i){SA.insert(str[i] – ‘a’ + 1);pos[cnt++] = 2;}SA.getsa(30);SA.getheight();SA.solve();}return 0;}
向上攀爬的。
