POJ 2774 后缀数组 （求最长公共子串）

 POJ—2774

 最近在学后缀数组，学了两天看了很多篇讲解博客也没有完全懂，也有没理解的地方。看了其他博客的题解，我发现初学后缀数组大多都是这样，开始也不怎么理解，背模板，但是我认为题量上来了 见得多了，可能某一时刻突然就会豁然开朗，掌握了精髓。我认为这也是每个学习者的必经之路。

 

关于后缀数组的链接看了很多，看了几篇比较好的放在下面，我觉得百度百科讲的后缀数组也比较清楚，但是不适合一开始看，因为我就是一开始看啥也看不懂。。。我自己的感受是可以按这个顺序看：

1、彻底弄懂后缀数组   2、五分钟搞懂后缀数组！3、后缀数组算法总结  4、后缀数组百度百科 5、后缀数组的一些应用

对于这道题：

题意：给你两串字符，要你找出在这两串字符中都出现过的最长子串。

思路：先用个分隔符将两个字符串连接起来，再用后缀数组求出height数组的值，找出一个height值最大并且i与i-1的sa值分别在两串字符中就好。

网上写法大多一样，也是后缀数组的水题。我的写法用了kuangbin的模板，也可以看一下。

#include<iostream>
#include<stdio.h>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=200010;
char s1[maxn],s2[maxn];
int s[maxn];
int t1[maxn],t2[maxn];
int Rank[maxn],sa[maxn],c[maxn],height[maxn];
bool cmp(int *r,int a,int b,int l)
{
    return r[a]==r[b]&&r[a+l]==r[b+l];
}
void da(int *r,int *sa,int n,int m)
{
    int i,j,p,*x=t1,*y=t2;
    for(i=0;i<m;i++) c[i]=0;
    for(i=0;i<n;i++) c[x[i]=r[i]]++;
    for(i=1;i<m;i++) c[i]+=c[i-1];
    for(i=n-1;i>=0;i--) sa[--c[x[i]]]=i;
    for(j=1;j<=n;j<<=1)
    {
        p=0;
        for(i=n-j;i<n;i++) y[p++]=i;;
        for(i=0;i<n;i++) if(sa[i]>=j) y[p++]=sa[i]-j;

        for(i=0;i<m;i++) c[i]=0;
        for(i=0;i<n;i++) c[x[y[i]]]++;
        for(i=1;i<m;i++) c[i]+=c[i-1];
        for(i=n-1;i>=0;i--) sa[--c[x[y[i]]]]=y[i];
        swap(x,y);
        p=1;
        x[sa[0]]=0;
        for(i=1;i<n;i++)
            x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
        if(p>=n) break;
        m=p;

    }
    int k=0;
    n--;
    for(i=0;i<=n;i++)
        Rank[sa[i]]=i;
    for(i=0;i<n;i++)
    {
        if(k) k--;
        j=sa[Rank[i]-1];
        while(r[i+k]==r[j+k])
            k++;
        height[Rank[i]]=k;
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>s1>>s2;
    int len1=strlen(s1);
    int len2=strlen(s2);
    int n=0;
    for(int i=0;i<len1;i++)
        s[n++]=s1[i]-'a'+1;
    s[n++]=30;//两串之间要有分隔符
    for(int i=0;i<len2;i++)
        s[n++]=s2[i]-'a'+1;
    s[n]=0;//末尾加0
    da(s,sa,n+1,31);//这里n+1是要包含末尾添加的0，m=31是因为要m要比串中每一位都大。
    int maxx=0;
    for(int i=2;i<n;i++)
    {
        if(height[i]>maxx)
        {
            if(0<=sa[i-1]&&sa[i-1]<len1&&sa[i]>len1)
                maxx=height[i];
            if(0<=sa[i]&&sa[i]<len1&&sa[i-1]>len1)
                maxx=height[i];
        }
    }
    cout<<maxx<<endl;
    return 0;
}