学会 SAM，做完这几道题目就足够了

ACM算法日常

发布于 2021-09-07 14:55:00

4280

发布于 2021-09-07 14:55:00

文章被收录于专栏：ACM算法日常

上周我们讲解了 sam 的基本原理，这一周，我们将把目光转向他的应用，主要通过题目讲解。

后缀自动机三·重复旋律6

Hihocoder1449

题意

字符串

中，求出长度为

k(1\le k\le |S|)

的子串出现次数最多的出现了几次。

分析

每个状态

所表示的所有子串的出现次数都相同。

我们把原始点（没有被拆分，或者拆分前的点）标记为

，其余为

。

如果一个状态

出现了，显然它的所有

link

前缀都出现了。

利用拓扑序，做一个前缀和，显然就是每个状态的出现次数。

每个状态

，所代表的子串的长度范围为

[len[link[x]]],len[x]

。

又显然，不同长度的最大出现次数递减，所以我们只需要在

len[x]

处打标记，再倒着更新一遍就好了。

#include<bits/stdc++.h>
#define LL long long
using namespace std;
#define N 2000010
const int M=N<<1;

struct sam
{
    int t[M][26],len[M]={-1},fa[M],sz=2,last=1,f[M];
    void init(){memset(t,0,(sz+10)*sizeof t[0]);sz=2;last=1;}
    void ins(int ch)
    {
        int p=last,np=last=sz++;f[np]=1;
        len[np]=len[p]+1;
        for (;p&&!t[p][ch];p=fa[p]) t[p][ch]=np;
        if (!p) {fa[np]=1;return;}
        int q=t[p][ch];
        if (len[p]+1==len[q]) fa[np]=q;
        else
        {
            int nq=sz++;len[nq]=len[p]+1;
            memcpy(t[nq],t[q],sizeof t[0]);
            fa[nq]=fa[q];
            fa[np]=fa[q]=nq;
            for (;t[p][ch]==q;p=fa[p]) t[p][ch]=nq;
        }
    }
    int c[M]={1},a[M];
    void rsort()
    {
        for (int i=1;i<sz;i++) c[i]=0;
        for (int i=1;i<sz;i++) c[len[i]]++;
        for (int i=1;i<sz;i++) c[i]+=c[i-1];
        for (int i=1;i<sz;i++) a[--c[len[i]]]=i;
    }
}a;

int n,ans[N];
char s[N];

int main()
{
    scanf("%s",s);
    n=strlen(s);
    a.init();
    for (int i=0;i<n;i++)
        a.ins(s[i]-'a');
    a.rsort();
    for (int i=a.sz-1;i>=1;i--)
        a.f[a.fa[a.a[i]]]+=a.f[a.a[i]];
    memset(ans,0,sizeof(ans));
    for (int i=1;i<a.sz;i++)
        ans[a.len[i]]=max(ans[a.len[i]],a.f[i]);
    for (int i=n;i>1;i--)
        ans[i-1]=max(ans[i-1],ans[i]);
    for (int i=1;i<=n;i++)
        printf("%d\n",ans[i]);
    return 0;
}

后缀自动机四·重复旋律7

Hihocoder1457

题意

求多串的所有不同子串的数（把一个由数字构成的字符串看成数）和。

分析

用一个特殊字符分隔不同的字符串，依次插入 SAM 。

从前往后枚举状态，后一个状态所表示的子串数和，无非是传递向它的那个状态的所有数

\times 10

再加上上一个状态的子串数量

\times

转移边。

所以，只需要根据字典序从前往后处理即可。

#include<bits/stdc++.h>
#define LL long long
using namespace std;
#define N 2000010
const int M=N<<1;

struct sam
{
    int t[M][26],len[M]={-1},fa[M],sz=2,last=1,f[M];
    void init(){memset(t,0,(sz+10)*sizeof t[0]);sz=2;last=1;}
    void ins(int ch)
    {
        int p=last,np=last=sz++;f[np]=1;
        len[np]=len[p]+1;
        for (;p&&!t[p][ch];p=fa[p]) t[p][ch]=np;
        if (!p) {fa[np]=1;return;}
        int q=t[p][ch];
        if (len[p]+1==len[q]) fa[np]=q;
        else
        {
            int nq=sz++;len[nq]=len[p]+1;
            memcpy(t[nq],t[q],sizeof t[0]);
            fa[nq]=fa[q];
            fa[np]=fa[q]=nq;
            for (;t[p][ch]==q;p=fa[p]) t[p][ch]=nq;
        }
    }
    int c[M]={1},a[M];
    void rsort()
    {
        for (int i=1;i<sz;i++) c[i]=0;
        for (int i=1;i<sz;i++) c[len[i]]++;
        for (int i=1;i<sz;i++) c[i]+=c[i-1];
        for (int i=1;i<sz;i++) a[--c[len[i]]]=i;
    }
}a;

int n,m,ans[N];
char s[N];
const LL mo=1000000007;
LL f[M],c[M];

int main()
{
    scanf("%d",&n);
    a.init();
    for (int i=1;i<=n;i++)
    {
        scanf("%s",s+1);
        m=strlen(s+1);
        for (int j=1;j<=m;j++)
            a.ins(s[j]-'0');
        if (i<n) a.ins(10);
    }
    a.rsort();
    memset(f,0,sizeof(f));
    memset(c,0,sizeof(c));
    c[1]=1;
    for (int i=1;i<a.sz;i++)
    {
        int x=a.a[i];
        for (int j=0;j<10;j++)
            if (a.t[x][j])
                c[a.t[x][j]]+=c[x],
                f[a.t[x][j]]=(f[a.t[x][j]]+(f[x]*10LL%mo+((LL)j)*(c[x])%mo))%mo;
    }
    LL ans=0;
    for (int i=1;i<a.sz;i++)
        ans=(ans+f[i])%mo;
    cout<<ans<<endl;
    return 0;
}

后缀自动机五·重复旋律8

Hihocoder1465

题意

求若干串

在另一个长串

中各自作为子串出现的次数，匹配的方式为“循环同构”。

分析

#include<bits/stdc++.h>
#define LL long long
using namespace std;
#define N 2000010
const int M=N<<1;

struct sam
{
    int t[M][26],len[M]={-1},fa[M],sz=2,last=1,f[M],v[M];
    void init(){memset(t,0,(sz+10)*sizeof t[0]);sz=2;last=1;}
    void ins(int ch)
    {
        int p=last,np=last=sz++;f[np]=1;
        len[np]=len[p]+1;
        for (;p&&!t[p][ch];p=fa[p]) t[p][ch]=np;
        if (!p) {fa[np]=1;return;}
        int q=t[p][ch];
        if (len[p]+1==len[q]) fa[np]=q;
        else
        {
            int nq=sz++;len[nq]=len[p]+1;
            memcpy(t[nq],t[q],sizeof t[0]);
            fa[nq]=fa[q];
            fa[np]=fa[q]=nq;
            for (;t[p][ch]==q;p=fa[p]) t[p][ch]=nq;
        }
    }
    int c[M]={1},a[M];
    void rsort()
    {
        for (int i=1;i<sz;i++) c[i]=0;
        for (int i=1;i<sz;i++) c[len[i]]++;
        for (int i=1;i<sz;i++) c[i]+=c[i-1];
        for (int i=1;i<sz;i++) a[--c[len[i]]]=i;
    }
}a;

int n,m;
char s[200010];

int main()
{
    scanf("%s",s+1);
    n=strlen(s+1);
    a.init();
    for (int i=1;i<=n;i++)
        a.ins(s[i]-'a');
    a.rsort();
    for (int i=a.sz-1;i>=1;i--)
        a.f[a.fa[a.a[i]]]+=a.f[a.a[i]];
    /*for (int i=1;i<a.sz;i++)
        for (int j=0;j<26;j++)
            if (a.t[i][j]) cout<<i<<" "<<j<<" "<<a.t[i][j]<<endl;*/
    scanf("%d",&m);
    while(m--)
    {
        for (int i=1;i<a.sz;i++)
            a.v[i]=1;
        scanf("%s",s+1);
        n=strlen(s+1);
        for (int i=n+1;i<2*n;i++)
            s[i]=s[i-n];
        s[2*n]=0;
        int u=1,l=0;LL ans=0;
        for (int i=1;i<2*n;i++)
        {
            int x=s[i]-'a';
            if (a.t[u][x]) u=a.t[u][x],l++;
            else
            {
                while(u>1&&!a.t[u][x]) u=a.fa[u];
                if (!a.t[u][x]) u=1,l=0;
                else l=a.len[u]+1,u=a.t[u][x];
            }
            //cout<<u<<" "<<l<<endl;
            if (l>=n)
            {
                while(u>1&&a.len[a.fa[u]]>=n) u=a.fa[u],l=a.len[u];
                ans+=(LL)a.f[u]*a.v[u];a.v[u]=0;
                //cout<<u<<" "<<l<<" "<<ans<<endl;
            }
        }
        printf("%lld\n",ans);
    }
    return 0;
}

后缀自动机六·重复旋律9

Hihocoder1466

分析

我们知道在 SAM 上从初始状态

t_0

到某一个状态

的一条合法路径表示了一个子串。

所以题目可以转变为在两个 DAG 上有两个初始点，每次每个人可以选择一个点向后转移一步，第一个没有路可走的人就输了。

这部分可以用 SG 函数得到：

这是一个显然的 DAG 上 SG 函数问题。两个 DAG 的问题就是组合起来，用异或判断是否为

即可。

于是先手的必胜初始态就是两个 DAG 中 SG 值不同的 pair 。因为要求字典序的第

大，于是需要计数。

首先肯定是对于每一个字符串

对应的 SAM 上的状态计算其中一个元素为这个想状态的合法 pair 数量，也就是统计

对应的 SAM 上 SG 值不同的个数。

根据这个值，我们求一个 DAG 上的前缀和，就能贪心的走，求出字典序第

大的了。

在完成第一个字符串的情况下，我们要继续完成第二个字符串。

因为第一个字符串已经确定了，那么第一个字符串对应的 SG 值也就确定了，于是对应第二个字符串就是要找到字典序满足要求，且 SG 值不等于第一个字符串的。

和上面类似的预处理 DAG 上前缀和，贪心的确定字典序对应的字符串即可。

要注意答案可能会爆 long long ，巨坑，对拍以后才发现这个问题。

#include<bits/stdc++.h>
#define LL long long
using namespace std;
#define N 2000010
const int M=N<<1;

struct sam
{
    int t[M][26],len[M]={-1},fa[M],sz=2,last=1,f[M],sg[M];
    void init()
    {
        memset(t,0,(sz+10)*sizeof t[0]);
        sz=2;last=1;
    }
    void ins(int ch)
    {
        int p=last,np=last=sz++;f[np]=1;
        len[np]=len[p]+1;
        for (;p&&!t[p][ch];p=fa[p]) t[p][ch]=np;
        if (!p) {fa[np]=1;return;}
        int q=t[p][ch];
        if (len[p]+1==len[q]) fa[np]=q;
        else
        {
            int nq=sz++;len[nq]=len[p]+1;
            memcpy(t[nq],t[q],sizeof t[0]);
            fa[nq]=fa[q];
            fa[np]=fa[q]=nq;
            for (;t[p][ch]==q;p=fa[p]) t[p][ch]=nq;
        }
    }
    int c[M]={1},a[M];
    void rsort()
    {
        for (int i=1;i<sz;i++) c[i]=0;
        for (int i=1;i<sz;i++) c[len[i]]++;
        for (int i=1;i<sz;i++) c[i]+=c[i-1];
        for (int i=1;i<sz;i++) a[--c[len[i]]]=i;
    }
    void getsg()
    {
        for (int x=sz-1;x>=1;x--)
        {
            set<int> S;
            for (int i=0;i<26;i++)
                if (t[a[x]][i]) S.insert(sg[t[a[x]][i]]);
            int z=0;
            while(S.count(z)>0) z++;
            sg[a[x]]=z;
        }
    }
}a,b;

LL k,suma,sumb,sga[M],sgb[M],sum[M];
int n,m;
char s[100010];

void dfsa()
{
    for (int x=a.sz-1;x>=1;x--)
    {
        for (int i=0;i<26;i++)
            if (a.t[a.a[x]][i])
            {
                sum[a.a[x]]+=sum[a.t[a.a[x]][i]];
                if (sum[a.a[x]]>k) sum[a.a[x]]=k+1;
            }
    }
}

void dfsb()
{
    for (int x=b.sz-1;x>=1;x--)
    {
        for (int i=0;i<26;i++)
            if (b.t[b.a[x]][i])
            {
                sum[b.a[x]]+=sum[b.t[b.a[x]][i]];
                if (sum[b.a[x]]>k) sum[b.a[x]]=k+1;
            }
    }
}

int main()
{
    scanf("%lld",&k);
    scanf("%s",s+1);
    n=strlen(s+1);a.init();
    for (int i=1;i<=n;i++)
        a.ins(s[i]-'a');
    scanf("%s",s+1);
    m=strlen(s+1);b.init();
    for (int i=1;i<=m;i++)
        b.ins(s[i]-'a');
    a.rsort(),b.rsort();
    a.getsg();
    b.getsg();
    memset(sga,0,sizeof(sga));
    memset(sgb,0,sizeof(sgb));
    suma=1,sumb=1;
    for (int i=2;i<a.sz;i++)
        sga[a.sg[i]]+=a.len[i]-a.len[a.fa[i]],
        suma+=(LL)a.len[i]-a.len[a.fa[i]];
        //cout<<i<<" "<<a.len[i]-a.len[a.fa[i]]<<endl;
    for (int i=2;i<b.sz;i++)
        sgb[b.sg[i]]+=b.len[i]-b.len[b.fa[i]],
        sumb+=(LL)b.len[i]-b.len[b.fa[i]];
    sga[a.sg[1]]++;sgb[b.sg[1]]++;
    for (int i=1;i<a.sz;i++)
        sum[i]=((LL)(sumb-sgb[a.sg[i]]));
    dfsa();
    int x=1,y=0;
    //cout<<sum[1]<<endl;
    if (sum[1]<k) {puts("NO");return 0;}
    int SG;
    while(x!=y)
    {
        y=x;
        if (sumb-sgb[a.sg[x]]>=k){SG=a.sg[x];break;}
        k-=(LL)(sumb-sgb[a.sg[x]]);
        //cout<<k<<endl;
        for (int j=0;j<26;j++)
            if (sum[a.t[x][j]]>=k) {x=a.t[x][j];putchar(j+'a');break;}
            else k-=sum[a.t[x][j]];
    }
    puts("");
    for (int i=1;i<b.sz;i++)
        if (b.sg[i]!=SG) sum[i]=1;else sum[i]=0;
    dfsb();
    x=1,y=0;
    while(x!=y)
    {
        y=x;
        if ((b.sg[x]!=SG)>=k) break;
        k-=(LL)(b.sg[x]!=SG);
        //cout<<k<<endl;
        for (int j=0;j<26;j++)
            if (sum[b.t[x][j]]>=k) {x=b.t[x][j];putchar(j+'a');break;}
            else k-=sum[b.t[x][j]];
    }
    puts("");
    return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2021-08-22，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自 ACM算法日常微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度