后缀数组 模板 HDU 1403 HDU 6194

HDU 1403

题意: 给出两个字符串, 求他们的最长公共子串。

思路: 两个字符串的最长公共子串长度显然就是两个字符串的所有后缀中的最长公共前缀长度。

AC code：

#include<bits/stdc++.h>
#define mem(a,b) memset((a),b,sizeof(a))
typedef long long ll;
const int N=200010;
using namespace std;
char s[200010];
int sa[N],t1[N],t2[N],c[N],Rank[N],height[N];
//rank[i] 第i个后缀的排名, sa[i] 排名为i的后缀的位置,height[i]为sa[i]和sa[i-1]的最长公共前缀(LCP)长度
void build_sa(int n,int m)
{
	//构造从0开始，长度为n的字符串s的后缀数组，每个字符值必须为0~m-1
    int i,p,*x=t1,*y=t2;
    for(i=0;i<m;i++)    c[i]=0;
    for(i=0;i<n;i++)    c[x[i]=s[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(int 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]]=y[sa[i-1]]==y[sa[i]] && y[sa[i-1]+j]==y[sa[i]+j]?p-1:p++;
        if(p>=n)    break;
        m=p;
    }
}
void getHeight(int n)
{
    //得到从0开始，长度为n的字符串s的height数组
    //height[i]为sa[i]和sa[i-1]的最长公共前缀(LCP)长度
    int i,j,k=0;
    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(s[i+k]==s[j+k])k++;
        height[Rank[i]]=k;
    }
}
int main()
{
    while(~scanf("%s",s))
    {
        int len1=strlen(s);
        s[len1]='$';
        scanf("%s",s+len1+1);
        int len2=strlen(s);
        build_sa(len2,'z'+1);
        getHeight(len2);
        int ans=0;
        for(int i=1;i<len2;i++)
        {
            if(sa[i]>len1&&sa[i-1]<len1)
                ans=max(ans,height[i]);
            if(sa[i]<len1&&sa[i-1]>len1)
                ans=max(ans,height[i]);
        }
        printf("%d\n",ans);
    }
    return 0;
}

HDU 6194

网上找的博客，再结合自己的博客，瞎改一番，过了。

#include<bits/stdc++.h>
using namespace std;
#define N 500000
int Rank[N],sa[N],height[N],f[N][50];
int t1[N],t2[N],c[N];
char s[N];
void build_sa(int n,int m)
{
	//构造从0开始，长度为n的字符串s的后缀数组，每个字符值必须为0~m-1
    int i,p,*x=t1,*y=t2;
    for(i=0;i<m;i++)    c[i]=0;
    for(i=0;i<n;i++)    c[x[i]=s[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(int 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]]=y[sa[i-1]]==y[sa[i]] && y[sa[i-1]+j]==y[sa[i]+j]?p-1:p++;
        if(p>=n)    break;
        m=p;
    }
}
void getHeight(int n)
{
    //得到从0开始，长度为n的字符串s的height数组
    //height[i]为sa[i]和sa[i-1]的最长公共前缀(LCP)长度
    int i,j,k=0;
    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(s[i+k]==s[j+k])k++;
        height[Rank[i]]=k;
    }
}
void ST_prework(int n)
{
    for(int i=0;i<=n;i++) //////// n n-1
        f[i][0]=height[i];
    int t=log(n)/log(2)+1;
    for(int j=1;j<t;j++)
          for(int i=2;i+(1<<j)-1<=n;i++)    ////////////这一句
            f[i][j]=min(f[i][j-1],f[i+(1<<(j-1))][j-1]);
}
int ST_query(int l,int r)
{
    if(l==r) return strlen(s+sa[l]);
    l++;r++;
    int k=log(r-l)/log(2);    ////// r-l  r-l+1
    return min(f[l][k],f[r-(1<<k)][k]);
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int k;
        scanf("%d",&k);
        scanf("%s",s);
        int n=strlen(s);
        build_sa(n+1,500); ///////////// n n+1
        getHeight(n);
        ST_prework(n);
        int ans=0;
        for(int i=1;i+k-1<=n;i++)
        {
            int l=i,r=i+k-1;
            int cnt=ST_query(l,r);
            if(l-1>=1)
                cnt-=ST_query(l-1,r);
            if(r+1<=n)
                cnt-=ST_query(l,r+1);
            if(l-1>=1&&r+1<=n)
                cnt+=ST_query(l-1,r+1);
            ans+=cnt;
        }
        cout<<ans<<endl;
    }
}