hdu 1403

Time Limit: 8000/4000 MS (Java/Others)Memory Limit: 65536/32768 K (Java/Others)

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

bananacianaic

Sample Output

3

解决问题的想法：两个系列连接在一起，中间用$分开，然后构建后缀组，找到最大的height[]。详细构建后缀组，请参考刘汝佳的算法竞赛介绍经典-训练指南

#include<iostream>#include<cstdio>#include<cstring>const int maxn = 1000010;int s[maxn<<1],t[maxn<<1],t2[maxn<<1];int rank[maxn<<1],height[maxn<<1],sa[maxn<<1];int n,ans,buc[maxn];char str1[maxn],str2[maxn];void getsa(int m){int i,*x = t,*y = t2;for(i = 0; i < m; i++) buc[i] = 0;for(i = 0; i < n; i++) buc[x[i] = s[i]]++;for(i = 0; i < m; i++) buc[i] += buc[i-1];for(i = n-1; i >= 0; i--) sa[--buc[x[i]]] = i;for(int k = 1; k <= n; k = k << 1){int p = 0;for(i = n-k; i < n; i++) y[p++] = i;for(i = 0; i < n; i++) if(sa[i] >= k) y[p++] = sa[i] - k;for(i = 0; i < m; i++) buc[i] = 0;for(i = 0; i < n; i++) buc[x[y[i]]]++;for(i = 0; i < m; i++) buc[i] += buc[i-1];for(i = n-1; i >= 0; i--) sa[--buc[x[y[i]]]] = y[i];std::swap(x,y);p = 1, x[sa[0]] = 0;for(i = 1; i < n; i++)x[sa[i]] = y[sa[i]] == y[sa[i-1]] && y[sa[i]+k] == y[sa[i-1]+k] ? p-1:p++;if(p >= n) break;m = p;}}void getheight(){int i,j,k = 0;for(i = 1; i <= n; i++) rank[sa[i]] = i;for(i = 0; i < n; i++){if(k) k--;if(rank[i] == 0){height[rank[i]] = 0;continue;}j = sa[rank[i]-1];while(s[i+k] == s[j+k]) k++;height[rank[i]] = k;}}int main(){while(scanf("%s",str1)!=EOF){n = 0;int len = strlen(str1);for(int i = 0; str1[i] !=EOF){n = 0;int len = strlen(str1);for(int i = 0; str1[i] != '\0'; i++)s[n++] = str1[i];s[n] = '$';scanf("%sstr2);for(int i = 0; str2[i] != '\0'; i++)s[n++] = str2[i];s[n] = 0;ans = 0;getsa(128);getheight();for(int i = 1; i < n; i++){if((sa[i] > len && sa[i-1] < len) || (sa[i] < len && sa[i-1] > len)){if(height[i] > ans)ans = height[i];}}printf("%d\n",ans);}return 0;}