http://acm.hdu.edu.cn/showproblem.php?pid=1403
Longest Common Substring
Time Limit: 8000/4000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 3068 Accepted Submission(s): 1087
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.
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.
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
cianaic
Sample Output
3
思路：
构造后缀数组和Heigh数组，利用height数组和sa数组的性质求解参考
用后缀数组的另外一种实现方法，一直WA，下面我将AC代码和WA代码同时给出，求大神在WA代码给点意见
AC代码：
#include <iostream> using namespace std; #define maxn 1000001
#define cls(x) memset(x, 0, sizeof(x))
int wa[maxn],wb[maxn],wv[maxn],wss[maxn];
int cmp(int *r,int a,int b,int l)
{return r[a]==r[b]&&r[a+l]==r[b+l];} void da(char *r,int *sa,int n,int m)
{
cls(wa);
cls(wb);
cls(wv);
cls(wss);
int i,j,p,*x=wa,*y=wb,*t;
for(i=;i<m;i++) wss[i]=;
for(i=;i<n;i++) wss[x[i]=r[i]]++;
for(i=;i<m;i++) wss[i]+=wss[i-];
for(i=n-;i>=;i--) sa[--wss[x[i]]]=i;
for(j=,p=;p<n;j*=,m=p)
{
for(p=,i=n-j;i<n;i++) y[p++]=i;
for(i=;i<n;i++) if(sa[i]>=j) y[p++]=sa[i]-j;
for(i=;i<n;i++) wv[i]=x[y[i]];
for(i=;i<m;i++) wss[i]=;
for(i=;i<n;i++) wss[wv[i]]++;
for(i=;i<m;i++) wss[i]+=wss[i-];
for(i=n-;i>=;i--) sa[--wss[wv[i]]]=y[i];
for(t=x,x=y,y=t,p=,x[sa[]]=,i=;i<n;i++)
x[sa[i]]=cmp(y,sa[i-],sa[i],j)?p-:p++;
}
return;
}
int rank[maxn],height[maxn];
void calheight(char *r,int *sa,int n)
{
cls(rank);
cls(height);
int i,j,k=;
for(i=;i<n;i++) rank[sa[i]]=i;
for(i=;i<n;height[rank[i++]]=k)
for(k?k--:,j=sa[rank[i]-];r[i+k]==r[j+k]&&i!=j;k++);
return;
} char ca[maxn * ];
int sa[maxn]; int main()
{
while (cin >> ca)
{
int len = strlen(ca);
int lenstr1 = len;
ca[len] = '#';
cin >> (ca + len + ); len = strlen(ca);
da(ca, sa, len, ); int i;
calheight(ca,sa,len); int max = ;
//cout << ca << endl;
for (i = ; i < len; ++i)
{
if (height[i] > max)
{
if ((sa[i] > lenstr1 && sa[i - ] < lenstr1) || (sa[i - ] > lenstr1 && sa[i] < lenstr1))
{
max = height[i];
}
}
}
//for (int i = 0; i < len; ++i)
//cout << (ca + i) << endl;
cout << max << endl;
cls(ca);
}
return ;
}
WA到死的代码：
#include<iostream>
#include<stdio.h>
#include<string.h>
#define MAXN 100010 char str[MAXN*];
int s[MAXN*],sa[MAXN*],rank[MAXN*],trank[MAXN*],sum[MAXN*],tsa[MAXN*],height[MAXN*]; void sorting(int j,int len)//基数排序
{
int i;
memset(sum,,sizeof(sum));
for (i=; i<=len; i++) sum[ rank[i+j] ]++;
for (i=; i<=len; i++) sum[i]+=sum[i-];
for (i=len; i>; i--) tsa[ sum[ rank[i+j] ]-- ]=i;//对第二关键字计数排序，tsa代替sa为排名为i的后缀是tsa[i] memset(sum,,sizeof(sum));
for (i=; i<=len; i++) sum[ rank[i] ]++;
for (i=; i<=len; i++) sum[i]+=sum[i-];
for (i=len; i>; i--) sa[ sum[ rank[ tsa[i] ] ]-- ]= tsa[i]; //对第一关键字计数排序
//构造互逆关系
// for(i=1;i<=len;i++) printf("%d ",rank[i]); putchar(10);
} void getsa(int len){ memset(sum,,sizeof(sum));
memset(rank,,sizeof(rank));
memset(height,,sizeof(height));
memset(trank,,sizeof(trank));
memset(sa,,sizeof(sa));
memset(tsa,,sizeof(tsa)); int i;
for (i=; i<len; i++) {
trank[i+]=s[i];
}
for (i=; i<=len; i++) {
sum[ trank[i] ]++;
}
for (i=; i<=; i++) sum[i]+=sum[i-];
for (i=len; i>; i--) sa[ sum[ trank[i] ]-- ]=i; // for(i=1;i<=len;i++) printf("%d ",sa[i]);putchar(10); rank[ sa[] ]=; int p;
for (i=,p=; i<=len; i++)
{
if (trank[ sa[i] ]!=trank[ sa[i-] ]) p++;
rank[ sa[i] ]=p;
}//第一次的sa与rank构造完成 //rank1: 11211112 // for(i=1;i<=len;i++) printf("%d ",rank[i]); putchar(10); for (int j=; j<=len; j*=)
{
sorting(j,len);
trank[ sa[] ]=;
p=; //用trank代替rank
for (i=; i<=len; i++)
{
if ((rank[ sa[i] ]!=rank[ sa[i-] ]) || (rank[ sa[i]+j ]!=rank[ sa[i-]+j ])) p++;
trank[ sa[i] ]=p;//空间要开大一点，至少2倍
}
for (i=; i<=len; i++) rank[i]=trank[i];
}
} void getheight(int len)
{
for (int i=,j=; i<=len; i++)//用j代替上面的h数组
{
if (rank[i]==) continue;
for (; s[i+j-]==s[ sa[ rank[i]- ]+j- ]; ) j++;//注意越界之类的问题
height[ rank[i] ]=j;
if (j>) j--;
}
} int main(){ while(~scanf("%s",str)){
int i;
int len1 = strlen(str);
str[len1]='#';
for(i=;i<len1;i++){
s[i]=str[i]-'a'+;
}
s[len1] = '#';
scanf("%s",str+len1+);
int maxlen = strlen(str);
for(i=len1+;i<maxlen;i++){
s[i]=str[i]-'a'+;
}
s[maxlen]=;
getsa(maxlen);
getheight(maxlen);
int maks = ;
len1++;
for (i = ; i <= maxlen; ++i)
{
if (height[i] > maks)
{
if ((sa[i] > len1 && sa[i - ] < len1) || (sa[i - ] > len1 && sa[i] < len1))
{
maks = height[i];
}
}
}
printf("%d\n",maks);
}
return ;
}
无解WA，求大神指教！！！