Peter_Matthew的博客

后缀自动机

2019-01-19

本文共891字，大约需要阅读5分钟。

普通的后缀自动机

代码如下：
洛谷P3975 [TJOI2015]弦论

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include<bits/stdc++.h>
using namespace std;
const int N=2010000;
char s[N];
int fail[N],son[N][26],len[N],siz[N],sum[N];
int rt=1,lst=rt,tot=1,n,t[N],A[N],tp,k;
void insert(int c)
{
    int fa=lst,now=++tot;
    lst=now;
    len[now]=len[fa]+1;
    siz[now]=1;
    while(fa&&!son[fa][c])
        son[fa][c]=now,fa=fail[fa];
    if(!fa)
    {
        fail[now]=rt;
        return;
    }
    int x=son[fa][c],y=++tot;
    if(len[fa]+1==len[x])
    {
        fail[now]=x;
        tot--;
        return;
    }
    len[y]=len[fa]+1;
    fail[y]=fail[x];
    fail[x]=fail[now]=y;
    memcpy(son[y],son[x],sizeof(son[y]));
    while(fa&&son[fa][c]==x)
        son[fa][c]=y,fa=fail[fa];
}
void work()
{
    for(int i=1;i<=tot;i++)
        t[len[i]]++;
    for(int i=1;i<=tot;i++)
        t[i]+=t[i-1];
    for(int i=1;i<=tot;i++)
        A[t[len[i]]--]=i;
    for(int i=tot;i>=1;i--)
    {
        int now=A[i];
        if(tp)siz[fail[now]]+=siz[now];
        else siz[now]=1;
    }
    siz[rt]=0;
    for(int i=tot;i;i--)
    {
        sum[A[i]]=siz[A[i]];
        for(int j=0;j<26;j++)
            if(son[A[i]][j])
                sum[A[i]]+=sum[son[A[i]][j]];
    }
}
main()
{
    scanf("%s%d%d",s+1,&tp,&k);
    n=strlen(s+1);
    for(int i=1;i<=n;i++)
        insert(s[i]-'a');
    work();
    if(k>sum[rt])
    {
        printf("-1\n");
        return 0;
    }
    int now=rt;
    while((k-=siz[now])>0)
    {
        int p=0;
        while(k>sum[son[now][p]])k-=sum[son[now][p++]];
        now=son[now][p];
        putchar('a'+p);
    }
    return 0;
}

广义后缀自动机

代码如下：
洛谷P2336 [SCOI2012]喵星球上的点名

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
#include<bits/stdc++.h>
using namespace std;
const int N=600005;
char s[N];
int fail[N],len[N],siz[N],sum[N];
int rt=1,lst,tot=1,n,m,t[N],A[N],len1[N],len2[N],las[N];
int str[N],marked[N],ans[N];
map<int,int>son[N];
void insert(int c)
{
    int fa=lst,now=++tot;
    lst=now;
    len[now]=len[fa]+1;
    while(fa&&!son[fa][c])
        son[fa][c]=now,fa=fail[fa];
    if(!fa)
    {
        fail[now]=rt;
        return;
    }
    int x=son[fa][c],y=++tot;
    if(len[fa]+1==len[x])
    {
        fail[now]=x;
        tot--;
        return;
    }
    len[y]=len[fa]+1;
    fail[y]=fail[x];
    fail[x]=fail[now]=y;
    son[y]=son[x];
    while(fa&&son[fa][c]==x)
        son[fa][c]=y,fa=fail[fa];
}
void updata1(int x,int y)
{
    for(;x&&las[x]!=y;x=fail[x])
    {
        siz[x]++;
        las[x]=y;
    }
}
void updata2(int x,int y)
{
    for(;x&&las[x]!=y;x=fail[x])
    {
        ans[y]+=marked[x];
        las[x]=y;
    }
}
main()
{
    scanf("%d%d",&n,&m);
    int tmp=0;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&len1[i]);
        lst=rt;
        for(int j=1;j<=len1[i];j++)
        {
            scanf("%d",&str[++tmp]);
            insert(str[tmp]);
        }
        scanf("%d",&len2[i]);
        lst=rt;
        for(int j=1;j<=len2[i];j++)
        {
            scanf("%d",&str[++tmp]);
            insert(str[tmp]);
        }
    }
    tmp=0;
    memset(las,0,sizeof(las));
    for(int i=1;i<=n;i++)
    {
        for(int j=1,x=rt;j<=len1[i];j++)updata1(x=son[x][str[++tmp]],i);
        for(int j=1,x=rt;j<=len2[i];j++)updata1(x=son[x][str[++tmp]],i);
    }
    for(int i=1,le,x;i<=m;i++)
    {
        scanf("%d",&le);
        bool tag=0;x=rt;
        for(int j=1,d;j<=le;j++)
        {
            scanf("%d",&d);
            if(!tag)
            {
                if(son[x][d])
                    x=son[x][d];
                else
                    tag=1;
            }
        }
        if(!tag)
        {
            marked[x]++;
            printf("%d\n",siz[x]);
        }
        else
            printf("0\n");
    }
    tmp=0;
    memset(las,0,sizeof(las));
    for(int i=1;i<=n;i++)
    {
        for(int j=1,x=rt;j<=len1[i];j++)updata2(x=son[x][str[++tmp]],i);
        for(int j=1,x=rt;j<=len2[i];j++)updata2(x=son[x][str[++tmp]],i);
    }
    for(int i=1;i<=n;i++)
        printf("%d ",ans[i]);
    return 0;
}

知识共享许可协议

知识共享许可协议

本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。

当前页共有次阅读，条评论。
标签: 字符串
← 后缀数组 二维树状数组 →
赏
使用支付宝打赏
使用微信打赏

若你觉得我的文章对你有帮助，欢迎点击上方按钮对我打赏