【poj3415】Common Substrings

2015.06.17 08:14 Wed | 24次阅读 | 旧日oi | 固定链接 | 源码

给出两个串,问这两个串的所有的子串中(重复出现的,只要是位置不同就算两个子串),长度大于等于k的公共子串有多少个。串长<=100000
题解
已经基本理解了后缀自动机了~
把第一个串建成后缀自动机,从后往前扫一遍得到每个串出现了多少次,然后匹配第二个串,当lcs的长度>=K时,对当前点统计答案,同时也有可能要更新父亲节点的答案,但是如果一起更新会t,所以可以打个标记。
注意这题会有大写字母。

我的程序

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define N 200005
#define ll long long
int K,len,len2;
char s[N],s2[N];
struct sam
{
    int son[N][52],fa[N],len[N],flag[N],v[N],rk[N];
    int tot,last;
    long long ans,cnt[N];
    void init(int L)
    {
        for(int i=1;i<=2*L;i++) 
        {
            cnt[i]=flag[i]=v[i]=0;
            memset(son[i],0,sizeof(son[i]));
        }
        last=tot=1;ans=0;
    }
    void insert(int x)
    {
        int p=last,np=++tot;last=np;
        len[np]=len[p]+1;
        for(;p&&!son[p][x];p=fa[p]) son[p][x]=np;
        if(!p) fa[np]=1;
        else
        {
            int q=son[p][x];
            if(len[q]==len[p]+1) fa[np]=q;
            else
            {
                int nq=++tot;len[nq]=len[p]+1;
                fa[nq]=fa[q];fa[q]=fa[np]=nq;
                memcpy(son[nq],son[q],sizeof(son[q]));
                for(;p&&son[p][x]==q;p=fa[p]) son[p][x]=nq;
            }
        }
    }
    void solve(int L)
    {
        for(int i=1;i<=tot;i++) v[len[i]]++;
        for(int i=1;i<=L;i++) v[i]+=v[i-1];
        for(int i=tot;i;i--) rk[v[len[i]]--]=i;
        for(int now,p=1,i=0;i<L;i++)
        {
            if(isupper(s[i])) now=s[i]-'A';
            else now=s[i]-'a'+26;
            cnt[p=son[p][now]]=1;
        }
        for(int i=tot;i;i--) cnt[fa[rk[i]]]+=cnt[rk[i]];
        int lcs=0;
        for(int now,p=1,i=0;i<len2;i++)
        {
            if(isupper(s2[i])) now=s2[i]-'A';
            else now=s2[i]-'a'+26;
            if(son[p][now])
            {
                lcs++;
                p=son[p][now];
            }
            else
            {
                while(p&&!son[p][now]) p=fa[p];
                if(p)
                {
                    lcs=len[p]+1;
                    p=son[p][now];
                }
                else lcs=0,p=1;
            }
            if(lcs>=K)
            {
                ans+=(lcs-max(K,len[fa[p]]+1)+1)*cnt[p];
                if(K<=len[fa[p]]) flag[fa[p]]++;
            }
        }
        for(int k,i=tot;i;i--)
        {
            k=rk[i];
            ans+=flag[k]*(len[k]-max(K,len[fa[k]]+1)+1)*cnt[k];
            if(len[fa[k]]>=K) flag[fa[k]]+=flag[k];
        }
        printf("%lld\n",ans);
    }
}sam;
int main()
{
    //freopen("tt.in","r",stdin);
    while(scanf("%d",&K)&&K)
    {
        scanf("%s",s);len=strlen(s);sam.init(len);
        for(int i=0;i<len;i++) 
        {
            if(isupper(s[i])) sam.insert(s[i]-'A');
            else sam.insert(s[i]-'a'+26);
        }
        scanf("%s",s2);len2=strlen(s2);
        sam.solve(len);
    }
}```