未学习后缀自动机的话,可以去这里看一下
 
 
 

由于字符串变化多端,这里介绍一些\(SAM\)的简单应用,以增加一些理解;
 
 
 

后缀自动机的应用

 
 
 

本质不同子串的个数

我们有\(SA\)数组的做法,在\(SAM\)上也一样可做;

发现其实\(SAM\)上是没有重复子串的,我们只需要统计出\(SAM\)上所有的子串就可以了;

\[ans=\sum maxlen[i]-minlen[i]+1\]

 
 
 

统计子串出现次数

求出\(SAM\)上每个每个字串的出现次数;

其实就是求每个状态的\(endpos\)集合大小,怎么求呢?

首先每次新加的一个状态\(endpos\)至少有一;

另外的,对于一个状态,每一个\(link\)入边,都会对此状态产生贡献;

\(num[i]+=\sum_{link[j]=i}num[j]\)

这样就可以在\(link\)所构成的\(DAG\)上跑拓扑;

 
 
 

两个串的最长公共子串

\(eg.\) SP1811

\(SA\)过不了的那种,可以先在第一个串上建\(SAM\),因为所有子串都会在\(SAM\)上体现,我们可以考虑将第二个串在这个\(SAM\)进行匹配;

 
 
 

算法流程:

当前状态\(p\)(初始为\(1\)),待匹配的字符是\(S[i]\),已匹配的长度为\(len\)

  1. 如果\(trans[p][S[i]]!=0\),意味着有这个子串,将\(len++\),转移到下一个状态;
  2. 否则沿着\(link\)向前寻找:
    • 如果能找到一个状态\(p\),满足\(trans[p][S[i]]!=0\),则可以将\(len=maxlen[p]+1\),转移到\(trans[p][S[i]]\)
    • 否则\(len=0,p=1\)
  3. 更新答案;

时间复杂度是\(O(n)\)\(n\)是两个字符串的总长;

 
 

部分代码

void search(int n)
{
    int p=1;
    for(int i=1;i<=n;i++)
    {
        int c=s[i]-'a';
        if(trans[p][c]) len++,p=trans[p][c];
        else
        {
            for(;p&&!trans[p][c];p=link[p]);
            if(p) len=maxlen[p]+1,p=trans[p][c];
            else len=0,p=1;
        }
        ans=max(ans,len);
    }
}

 
 
 

多个串的最长公共子串

\(eg.\) SP1812

假设有\(k\)个长度为\(n\)的字符串;

 
 

介绍两种方法

 

1 O(nk^2)

类似于统计子串出现次数,对于加进去的第\(i\)个字符串,对每个状态的第\(i\)维打上标记,即\(num[x][i]=1\);

再用拓扑或深搜统计出每个状态在每个字符串里出现的次数;

如果存在一个状态\(x\),它的每一位都有值(即在每个字符串中都出现过),可以用它更新答案;

时间复杂度是\(O(nk^2)\),过不了那个例题,但很好理解;

深搜时的代码

inline void dfs(int x)
{
    for(int i=head[x];i;i=a[i].nxt)
    {
        dfs(a[i].to);
        for(int j=0;j<t;j++)//t是个数
            T.num[x][j]+=T.num[a[i].to][j];
    }
    bool fl=0;
    for(int j=0;j<t;j++)
        if(!T.num[x][j])
        {
            fl=1;
            break;
        }

    if(!fl) ans=max(ans,T.ml[x]);
}

 
 
 

2 O(nk)

 
 
 

另一种

由求两个串的情况拓展而来;

考虑在第一个串上建\(SAM\),把剩余的每个串都拿到\(SAM\)上去匹配一下;

每次匹配时,得到当前匹配,每个状态的最长匹配成功长度;

按照理想的情况,最后在每次匹配的最长长度中找一个最小值,就是某一状态的所有匹配的最长公共匹配成功长度;

 

但是会存在一个问题,如果状态\(x\)匹配成功了,其\(link[x]\)也一定存在\(x\)的匹配,我们没有到达过\(link[x]\),这一部分值就无从存在了,所以我们必须要更新\(link[x]\)

 

但由于\(link[x]\)自身长度的限制,我们应当把\(maxn[link[x]]=max(maxn[link[x]],min(maxn[x],maxlen[link[x]]))\)

(\(maxn[x]\)就是状态\(x\)的当前匹配的最长匹配成功长度)

 

为了保证这个过程更新完全,我们需要按拓扑序来更新,即先更新了\(x\)后才能更新\(link[x]\)

我们发现\(maxlen[x]>maxlen[link[x]]\),所以按照\(maxlen\)的排名更新就可以了,可以省去一次拓扑排序;

 

这样时间是\(O(nk)\)

有关代码

//这都在SAM结构体中
void topu()
{
    for(int i=1;i<=sz;i++) tub[ml[i]]++;
    for(int i=1;i<=sz;i++) tub[i]+=tub[i-1];
    for(int i=sz;i>=1;i--) b[tub[ml[i]]--]=i;
}
//类似于后缀数组,用一次基数排序得到拓扑序
void work()
{
    int l=0,p=1;
    for(int i=1;i<=n;i++)
    {
        int x=c[i]-'a';
        if(trans[p][x]) l++,p=trans[p][x];
        else
        {
            for(;p&&!trans[p][x];p=link[p]);
            if(p) l=ml[p]+1,p=trans[p][x];
            else l=0,p=1;
        }
        mas[p]=max(mas[p],l);
    }
    for(int i=sz;i>=1;i--)
    {
        int x=b[i],li=link[x];
        mas[li]=max(mas[li],min(mas[x],ml[li]));
        mis[x]=min(mis[x],mas[x]);
        mas[x]=0;
    }
}

 
 
 

字典序第k大子串

\(eg.\) P3675

有两种情况

当不合并本质相同的串时:

还是基于一个思想,\(SAM\)上的路径对应了一个一个的子串;

求第\(k\)大子串就是求第\(k\)大路径;

类似于二叉查找树的方法,如果我们能知道每个状态后连接了多少条路径的话,我们就可以把这个问题当成多叉查找树来做;

 

另外还需要考虑一个问题;

每个状态有多个\(endpos\),这相当与一个状态的副本数;

我们仍然记\(|endpos[i]|\)\(num[i]\)

将第\(i\)个状态的路径总数,扩展为经过这个状态的子串数,记为\(sum[i]\)

因为,状态自身就存在\(num[i]\)个子串,且排在后面继续匹配的得到的子串的前面;

 

可以得到

\[sum[i]=num[i]+\sum_{trans[i][j]=x}sum[j]\]

 

另一种情况:

合并本质相同的串;

其实就是把每个状态(除了起始状态)的\(num\)都置为\(1\)

 

\(code\)

#include<bits/stdc++.h>
#define ll long long
#define mp make_pair
using namespace std;
const int N=500010;
char c[N];
int n,ty,k;

struct SAM
{
    int sz,last;
    int tub[N<<1],b[N<<1];
    int num[N<<1],sum[N<<1];
    int link[N<<1],trans[N<<1][26],ml[N<<1];
    SAM(){sz=last=1;}

    void add(int id)
    {
        int x=++sz,p;
        ml[x]=ml[last]+1;
        num[x]=1;
        for(p=last;p&&!trans[p][id];p=link[p]) trans[p][id]=x;
        if(!p) link[x]=1;
        else
        {
            int q=trans[p][id];
            if(ml[q]==ml[p]+1) link[x]=q;
            else
            {
                int y=++sz;
                ml[y]=ml[p]+1;
                memcpy(trans[y],trans[q],sizeof trans[y]);
                link[y]=link[q];
                for(;p&&trans[p][id]==q;p=link[p]) trans[p][id]=y;
                link[x]=link[q]=y;
            }
        }
        last=x;
    }

    void topu()
    {
        for(int i=1;i<=sz;i++) tub[ml[i]]++;
        for(int i=1;i<=sz;i++) tub[i]+=tub[i-1];
        for(int i=sz;i>=1;i--) b[tub[ml[i]]--]=i;
    }

    void getsz()
    {
        for(int i=sz;i>=1;i--)
        {
            int x=b[i];
            sum[x]+=num[x];
            num[link[x]]+=num[x];
        }
        if(ty==0) for(int i=1;i<=sz;i++) sum[i]=num[i]=1;
    }

    void getsum()
    {
        num[1]=sum[1]=0;
        for(int i=sz;i>=1;i--)
        {
            int x=b[i];
            for(int j=0;j<26;j++)
                if(trans[x][j]) sum[x]+=sum[trans[x][j]];
        }
    }

}T;

inline void sol(int x,int k)
{
    if(k<=T.num[x]) return ;
    k-=T.num[x];
    for(int i=0;i<26;i++)
    {
        int y=T.trans[x][i];
        if(!y) continue;
        if(k>T.sum[y])
        {
            k-=T.sum[y];
        }
        else
        {
            printf("%c",'a'+i);
            sol(y,k);
            break;
        }
    }
}

int main()
{
    scanf("%s",c+1);
    scanf("%d%d",&ty,&k);
    n=strlen(c+1);
    for(int i=1;i<=n;i++)
        T.add(c[i]-'a');
    T.topu();
    T.getsz();
    T.getsum();
    if(T.sum[1]<k) printf("-1");
    else sol(1,k);

    return 0;
}
02-12 12:16
查看更多