ACM字符串题目及源代码

《ACM字符串题目及源代码》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、31zhxfl目录Hdu1403最长公共子串2Pku1743不可以重复的最长重复子串4Pku3261可以重叠k次的最长重复子串7Spoj694不相同的子串的个数10Hdu3068最长回文（扩展kmp）13Timus1297最长回文子串后缀数组解法16Pku3693重复次数最多的连续重复子串20nlogn后缀数组TLE22Kmp24SPOJ687重复次数最多的连续重复子串25Pku3693同上题一样原理29Pku3415长度不小于k的公共子串的个数2931zhxflHdu1403最长公共子串SampleInputbananacianaic SampleOutput3#

2、include#include#includeusingnamespacestd;#definemaxn200005intwa[maxn],wb[maxn],wv[maxn],wh[maxn];intcmp(int*r,inta,intb,intl){returnr[a]==r[b]&&r[a+l]==r[b+l];}voidda(char*r,int*sa,intn,intm){inti,j,p,*x=wa,*y=wb,*t;for(i=0;i

3、h[x[i]=r[i]]++;for(i=1;i=0;i--)sa[--wh[x[i]]]=i;for(j=1,p=1;pn)break;for(p=0,i=n-j;i=j)y[p++]=sa[i]-j;for(i=0;i

4、=0;i--)sa[--wh[wv[i]]]=y[i];for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1;i

5、k)31zhxflfor(k?k--:0,j=sa[rank[i]-1];r[i+k]==r[j+k];k++);return;}intjudge(inti,intn,int*sa){intt1,t2;if(sa[i]<=n)t1=1;elset1=0;if(sa[i-1]<=n)t2=1;elset2=0;if(t1!=t2)return1;elsereturn0;}charr[maxn];chartmp[maxn];intsa[maxn];intmain(){inti,j,n,m;//freopen("a.txt","r",stdin);while(scanf(

6、"%s%s",&r,&tmp)!=EOF){n=strlen(r);m=strlen(tmp);r[n]='';for(i=0,j=n+1;imax&&judge(i,

7、n-m-1,sa))max=height[i];printf("%d",max);}return0;}Pku1743不可以重复的最长重复子串TimeLimit:1000MSMemoryLimit:30000KDescription31zhxflAmusicalmelodyisrepresentedasasequenceofN(1<=N<=20000)notesthatareintegersintherange1..88,eachrepresentingakeyonthepiano.Itisunfortunatebuttruethatthisrepresent