字符串算法集锦

字数统计: 5.9k字   |   阅读时长: 32min

KMP

时间复杂度为O(n)的字符串匹配算法。

应用：

1.单一子串和模式串匹配

P3375 【模板】KMP字符串匹配

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
#include<bits/stdc++.h>
using namespace std;
int f[1001000];//fail数组下标从1开始 
char s1[1001000],s2[1001000];//字符串下表从0开始 
int l1,l2;
inline void kmp()
{
	for(register int i=1;i<l2;i++) //处理2~l2的fail数组(f[1]=0) 
	{
		int j=f[i];
		while(j&&s2[j]!=s2[i]) j=f[j];
		f[i+1]=(s2[j]==s2[i])?j+1:0;
	}
}
inline void get()
{
	int j=0;
	for(register int i=0;i<=l1;i++)
	{
		while(j&&s1[i]!=s2[j]) j=f[j];
		if(s1[i]==s2[j]) j++;
		if(j==l2) printf("%d\n",i-j+2);
	}
}
int main()
{
	scanf("%s",s1);//主串 
	scanf("%s",s2);//模式串 
	l1=strlen(s1);
	l2=strlen(s2);
	kmp();
	get();
	for(register int i=1;i<=l2;i++) printf("%d ",f[i]);
	return 0;
}

2.求最小循环节

SP263 PERIOD - Period

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
#include<bits/stdc++.h>
using namespace std;
int T,n;
char s[1001000];
int f[1001000];
inline void kmp()
{
	memset(f,0,sizeof(f));
	int j;
	for(register int i=1;i<n;i++)
	{
		j=f[i];
		while(j&&s[i]!=s[j]) j=f[j];
		f[i+1]=(s[i]==s[j])?j+1:0;
		if(f[i+1]&&((i+1)%(i+1-f[i+1]))==0)
			printf("%d %d\n",i+1,(i+1)/(i+1-f[i+1]));
	}
}
int main()
{
	scanf("%d",&T);
	for(register int t=1;t<=T;t++)
	{
		printf("Test case #%d\n",t);
		scanf("%d",&n);scanf("%s",s);
		kmp();
	}
	return 0;
}

很显然，如果该字符串有循环节且$f[i]!=0$时$i-f[i]$即为该字符串的最小循环节。

3.求一个字符串所有相同的前后缀

P2375 [NOI2014]动物园

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int p = 1e9+7;
int n,len;
char s[1001000];
int f[1001000],num[1001000];//这里num并不直接是该题的答案，它代表1~n中所有的相等前后缀(可重复)。
inline void getfail(int len)
{
	memset(f,0,sizeof(f));
	memset(num,0,sizeof(num));
	num[0]=0;num[1]=1;
	ll ans=1;
	for(register int i=1;i<len;i++)
	{
		int j=f[i];
		while(j&&s[i]!=s[j]) j=f[j];
		f[i+1]=(s[i]==s[j])?j+1:0;
		j=f[i+1];num[i+1]=num[j]+1;
	}
	int j=0;
	for(register int i=1;i<len;i++)
	{
		while(j&&s[i]!=s[j]) j=f[j];
		if(s[i]==s[j]) j++;
		while(j*2>i+1) j=f[j];
		ans*=(num[j]+1),ans%=p;
	}
	printf("%lld\n",ans);
}
int main()
{
	scanf("%d",&n);
	while(n--)
	{
		scanf("%s",s);
		len=strlen(s);
		getfail(len);
	}
	return 0;
}

这道题不是单一的求一个字符串的答案，而是一个字符串所有前缀答案的乘积。但本质上还是对next数组的应用。

思考可得$next[i]$,$next[next[i]]$,$next[next[next[i]]]$,…都是前缀1~i的相等前后缀，递归统计即可。

然而如果输入n个’a’的时候，算法便被卡成了O(n^2)了，但我们发现每次递归都会有大量重复计算的相等前后缀，因此求完next数组后，再一次遍历整个字符串，不过这回我们不再把变量j从新赋值，接着用上一次的值，并判断其是否合法，这样便省掉了许多重复操作。

AC自动机

KMP+trie树

应用

1.多个模式串和主串进行匹配

P3808 【模板】AC自动机(简单版)

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
#include<bits/stdc++.h>
using namespace std;
int n;
char s[1001000];
int ch[1001000][26],tot,tag[1001000];

inline void ins()
{
	int n=strlen(s),x=0;
	for(register int i=0;i<n;i++)
	{
		int t=s[i]-'a';
		if(!ch[x][t]) ch[x][t]=++tot;
		x=ch[x][t];
	}
	tag[x]++;
}

int f[1001000];//以该节点为结尾的子串的 最长与任意模式串的前缀相等的 后缀。 
inline void getfail()
{
	queue<int> q;
	for(register int i=0;i<26;i++) 
	if(ch[0][i]) q.push(ch[0][i]);
	while(!q.empty())
	{
		int x=q.front();
		q.pop();
		for(register int i=0;i<26;i++)
		{
			if(ch[x][i]) f[ch[x][i]]=ch[f[x]][i],q.push(ch[x][i]);
			else ch[x][i]=ch[f[x]][i];
		}
	}
}

inline void find()
{
	int n=strlen(s),x=0,ans=0;
	for(register int i=0;i<n;i++)
	{
		x=ch[x][s[i]-'a'];
		for(register int j=x;j&&~tag[j];j=f[j]) ans+=tag[j],tag[j]=-1;
	}
	printf("%d\n",ans);
}

int main()
{
	scanf("%d",&n);
	for(register int i=1;i<=n;i++)
	{
		scanf("%s",s);
		ins();
	}
	getfail();
	scanf("%s",s);
	find();
	return 0;
}

这位大佬的文章挺详细的。

P3796 【模板】AC自动机（加强版）

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
#include<bits/stdc++.h>
using namespace std;
char s1[1001000];
char s2[200][100];
int f[500000],l[500000];
int ch[500000][26],tot,tag[500000];
int ans[200];

inline void ins(int idx)
{
	int x=0,n=strlen(s2[idx]);
	for(register int i=0;i<n;i++)
	{
		int t=s2[idx][i]-'a';
		if(!ch[x][t]) ch[x][t]=++tot;
		x=ch[x][t];
	}
	tag[x]=idx;
}

inline void getfail()
{
	queue<int> q;
	for(register int i=0;i<26;i++)
	if(ch[0][i]) q.push(ch[0][i]);
	while(!q.empty())
	{
		int x=q.front();
		q.pop();
		for(register int i=0;i<26;i++)
		{
			if(tag[ch[f[x]][i]]) l[ch[x][i]]=ch[f[x]][i];
			else l[ch[x][i]]=l[ch[f[x]][i]];
			if(ch[x][i]) f[ch[x][i]]=ch[f[x]][i],q.push(ch[x][i]);
			else ch[x][i]=ch[f[x]][i];
		}
	}
}

inline void find()
{
	int n=strlen(s1),x=0;
	for(register int i=0;i<n;i++)
	{
		x=ch[x][s1[i]-'a'];
		for(register int j=x;j;j=l[j]) ans[tag[j]]++;
	}
}

int n;

int main()
{
	while(scanf("%d",&n)&&n!=0)
	{
		memset(tag,0,sizeof(tag));
		memset(ch,0,sizeof(ch));
		memset(f,0,sizeof(f));
		memset(l,0,sizeof(l));
		memset(ans,0,sizeof(ans));
		for(register int i=1;i<=n;i++)
		scanf("%s",s2[i]),ins(i);
		getfail();
		scanf("%s",s1);
		find();
		int mx=*max_element(ans+1,ans+1+n);
		printf("%d\n",mx);
		for(register int i=1;i<=n;i++) if(ans[i]==mx) printf("%s\n",s2[i]);
		
	}
	return 0;
}

这道题新引入了一个优化，$l[x]$表示以节点x为结尾的后缀所包含的最长单词。这样就可以快速找到单词节点而不用一个一个的跳fail数组了。

P2292[HNOI2004]L语言

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
#include<bits/stdc++.h>
using namespace std;

template<typename T>
inline void read(T &a)
{
	T f=1;a=0;char s=getchar();
	while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
	while(s<='9'&&s>='0'){a=a*10+s-'0';s=getchar();}
	a*=f;
}

int n,m;
int ch[10000][26],tot,tag[10000],len[10000];
int l[10000],f[10000];
char s[1100000];

inline void ins()
{
	int le=strlen(s),x=0;
	for(register int i=0;i<le;i++)
	{
		if(!ch[x][s[i]-'a']) ch[x][s[i]-'a']=++tot;
		x=ch[x][s[i]-'a'];
	}
	tag[x]=1;
	len[x]=le;
}

inline void getfail()
{
	queue<int> q;
	for(register int i=0;i<26;i++)
	if(ch[0][i]) q.push(ch[0][i]);
	while(!q.empty())
	{
		int x=q.front();
		q.pop();
		for(register int i=0;i<26;i++)
		{
			if(tag[ch[f[x]][i]]) l[ch[x][i]]=ch[f[x]][i];
			else l[ch[x][i]]=l[ch[f[x]][i]];
			if(ch[x][i]) f[ch[x][i]]=ch[f[x]][i],q.push(ch[x][i]);
			else ch[x][i]=ch[f[x]][i];
		}
	}
}

bool vis[1100000];

inline int find()
{
	memset(vis,0,sizeof(vis));
	vis[0]=1;
	int le=strlen(s),x=0;
	for(register int i=0;i<le;i++)
	{
		x=ch[x][s[i]-'a'];
		for(register int j=x;j;j=l[j])
		if(tag[j]&&vis[i-len[j]+1])
		{
			vis[i+1]=1;
			break;
		}
	}
	for(register int i=le;i;i--) if(vis[i]) return i;
}

int main()
{
	read(n),read(m);
	for(register int i=1;i<=n;i++) 
	{
		scanf("%s",s);
		ins();
	}
	getfail();
	for(register int i=1;i<=m;i++)
	{
		scanf("%s",s);
		printf("%d\n",find());
	}
	return 0;
}

这道题也是一道多个模式串和主串进行匹配的题，我们只需在主串进行匹配的同时，判断是否能通过模式串到达该位置。

2.在fail树(或l树)上跑树形DP

P2414 [NOI2011]阿狸的打字机

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
#include<bits/stdc++.h>
#define lowbit(x) (x&-x)
using namespace std;

template<typename T>
inline void read(T &a)
{
	T f=1;a=0;char s=getchar();
	while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
	while(s<='9'&&s>='0'){a=a*10+s-'0';s=getchar();}
	a*=f;
}

int ch[100100][26],tot,tag[100100];
int l[100100],f[100100],cnt,fa[100100];
char s[100100];
int m,ans[100100],num[100100],idx,ll[100100],rr[100100];
int tr[100100];
//num与tag互为反函数  tot:总结点数 cnt:单词数 fa[]与ch[][]互为反函数 ll[],rr[]:子树dfs序左右两端  tr:树状数组 
inline void modify(int x,int v)
{
	for(;x<=idx;x+=lowbit(x)) tr[x]+=v;
}

inline int query(int x)
{
	int sum=0;
	for(;x;x-=lowbit(x)) sum+=tr[x];
	return sum;
}

struct tree
{
	int ne,to;
}e[100100];

int head[100100],bcnt;

inline void add(int u,int v)
{
	e[++bcnt].to=v;
	e[bcnt].ne=head[u];
	head[u]=bcnt;
}

void dfs(int x)
{
	ll[x]=++idx;
	for(register int i=head[x];i;i=e[i].ne) dfs(e[i].to);
	rr[x]=idx;
}

struct node
{
	int x,y,id;
	bool operator < (const node &a) const{ return y<a.y;}
}q[100100];

inline void getfail()
{
	queue<int> q;
	for(register int i=0;i<26;i++)
	if(ch[0][i]) q.push(ch[0][i]);
	while(!q.empty())
	{
		int x=q.front();
		q.pop();
		for(register int i=0;i<26;i++)
		{
			if(tag[ch[f[x]][i]]) l[ch[x][i]]=ch[f[x]][i];
			else l[ch[x][i]]=l[ch[f[x]][i]];
			if(ch[x][i]) f[ch[x][i]]=ch[f[x]][i],q.push(ch[x][i]);
			else ch[x][i]=ch[f[x]][i];
		}
	}
}

int main()
{
	scanf("%s",s);
	int n=strlen(s),x=0;
	for(register int i=0;i<n;i++)
	{
		if(s[i]=='P') tag[x]=++cnt,num[cnt]=x;//单词树 
		else if(s[i]=='B') x=fa[x];
		else
		{
			if(!ch[x][s[i]-'a']) ch[x][s[i]-'a']=++tot,fa[tot]=x;
			x=ch[x][s[i]-'a'];
		}
	}
	getfail();
	for(register int i=1;i<=tot;i++) add(l[i],i);
	dfs(0);
	read(m);
	for(register int i=1;i<=m;i++) read(q[i].x),read(q[i].y),q[i].id=i;
	sort(q+1,q+1+m);
	for(register int i=1,p=1;i<=m;i=p)
	{
		for(register int j=num[q[i].y];j;j=fa[j])
		modify(ll[j],1);
		while(q[p].y==q[i].y)
		{
			ans[q[p].id]=query(rr[num[q[p].x]])-query(ll[num[q[p].x]]-1);
			p++;
		}
		memset(tr,0,sizeof(tr));
	}
	for(register int i=1;i<=m;i++) printf("%d\n",ans[i]);
	return 0;
}
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
113
114
115
116
117
#include<bits/stdc++.h>
#define lowbit(x) (x&-x)
using namespace std;

template<typename T>
inline void read(T &a)
{
	T f=1;a=0;char s=getchar();
	while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
	while(s<='9'&&s>='0'){a=a*10+s-'0';s=getchar();}
	a*=f;
}

int ch[100100][26],tot,tag[100100];
int l[100100],f[100100],cnt,fa[100100];
char s[100100];
int m,ans[100100],num[100100],idx,ll[100100],rr[100100];
int tr[100100],ql[100100],qr[100100],tmp[100100][26];
//num与tag互为反函数  tot:总结点数 cnt:单词数 fa[]与ch[][]互为反函数 ll[],rr[]:子树dfs序左右两端  tr:树状数组 
inline void modify(int x,int v)
{
	for(;x<=idx;x+=lowbit(x)) tr[x]+=v;
}

inline int query(int x)
{
	int sum=0;
	for(;x;x-=lowbit(x)) sum+=tr[x];
	return sum;
}

struct tree
{
	int ne,to;
}e[100100];

int head[100100],bcnt;

inline void add(int u,int v)
{
	e[++bcnt].to=v;
	e[bcnt].ne=head[u];
	head[u]=bcnt;
}

void dfs(int x)
{
	ll[x]=++idx;
	for(register int i=head[x];i;i=e[i].ne) dfs(e[i].to);
	rr[x]=idx;
}

struct node
{
	int x,y,id;
	bool operator < (const node &a) const{ return y<a.y;}
}q[100100];

inline void getfail()
{
	queue<int> q;
	for(register int i=0;i<26;i++)
	if(ch[0][i]) q.push(ch[0][i]);
	while(!q.empty())
	{
		int x=q.front();
		q.pop();
		for(register int i=0;i<26;i++)
		{
			if(tag[ch[f[x]][i]]) l[ch[x][i]]=ch[f[x]][i];
			else l[ch[x][i]]=l[ch[f[x]][i]];
			if(ch[x][i]) f[ch[x][i]]=ch[f[x]][i],q.push(ch[x][i]);
			else ch[x][i]=ch[f[x]][i];
		}
	}
}

void DFS(int x)
{
	modify(ll[x],1);
	if(tag[x])
	for(register int i=ql[tag[x]];i<=qr[tag[x]];i++)
	ans[q[i].id]=query(rr[num[q[i].x]])-query(ll[num[q[i].x]]-1);
	for(register int i=0;i<26;i++) if(tmp[x][i]) DFS(tmp[x][i]);
	modify(ll[x],-1);
}

int main()
{
	scanf("%s",s);
	int n=strlen(s),x=0;
	for(register int i=0;i<n;i++)
	{
		if(s[i]=='P') tag[x]=++cnt,num[cnt]=x;//单词树 
		else if(s[i]=='B') x=fa[x];
		else
		{
			if(!ch[x][s[i]-'a']) ch[x][s[i]-'a']=++tot,fa[tot]=x,tmp[x][s[i]-'a']=tot;
			x=ch[x][s[i]-'a'];
		}
	}
	getfail();
	for(register int i=1;i<=tot;i++) add(l[i],i);//当然也可以用 add(f[i],i);
	dfs(0);
	read(m);
	for(register int i=1;i<=m;i++) read(q[i].x),read(q[i].y),q[i].id=i;
	sort(q+1,q+1+m);
	for(register int i=1,p=1;i<=m;i=p)
	{
		ql[q[i].y]=i;
		while(q[p].y==q[i].y) p++;
		qr[q[i].y]=p-1;
	}
	DFS(0);
	for(register int i=1;i<=m;i++) printf("%d\n",ans[i]);
	return 0;
}

这道题我们引入了fail tree。

  • 在AC自动机中，我们知道，当我们从节点x出发一直沿着f指针进行跳跃直到0时，一路上所有单词节点都被包含在x在trie树中所表示的字符串中。
  • 所以当我们想要找trie树中某一字符串y所包含的某一模式串x的次数时，我们便可以在trie树上从该字符串的结尾点向上跳，每跳一个，我们便要记录$f[y]$,$f[f[y]]$,$f[f[f[y]]]$,…,是不是单词节点x。
  • 那问题如果反过来，询问一个模式串在其他几个模式串中出现过呢？
  • 这时我们就想到了可以以每条fail为边建一颗fail tree(因为每个节点有且仅有一条fail边对应树中每个节点有且仅有一个父亲节点)，此时我们可以直接统计以节点x为根的子树中有几个单词节点即可。
  • 好了，现在回到这道题上，对于询问(x,y),我们可以从单词y所对应的节点在trie上一直跳父边到0，并在每一节点上加上1，最后只需统计单词x所对应的节点为根的子树中有多少1即可。(见暴力70分)
  • 但是对于单词aaaab和aaaaaa等包含大量重复节点的询问，这样是非常浪费的，所以便有了正解中的第二遍在trie树上跑的dfs,这样便省去了多余的运算。

后缀自动机

将后缀树中相同结束位置的后缀节点合并为一个节点的最简状态自动机。

P3804 【模板】后缀自动机

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
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+10;
typedef long long ll;
char s[N];
int son[N<<1][26],link[N<<1],size[N<<1],l[N<<1];
int cnt=1,last=1;

inline void ins(int s)
{
	int np=++cnt,p=last;
	last=np;l[np]=l[p]+1;
	for(;!son[p][s]&&p;p=link[p]) son[p][s]=np;
	if(!p) link[np]=1;
	else
	{
		int q=son[p][s];
		if(l[q]==l[p]+1) link[np]=q;
		else
		{
			int nq=++cnt;
			l[nq]=l[p]+1;
			memcpy(son[nq],son[q],sizeof(son[q]));
			link[nq]=link[q];link[q]=link[np]=nq;
			for(;son[p][s]==q;p=link[p]) son[p][s]=nq;
		}
	}
	size[np]=1;
}

int tong[N<<1],sa[N<<1];
ll ans;

int main()
{
	scanf("%s",s+1);
	int n=strlen(s+1);
	for(register int i=1;i<=n;i++) ins(s[i]-'a');
	for(register int i=1;i<=cnt;i++) tong[l[i]]++;
	for(register int i=1;i<=cnt;i++) tong[i]+=tong[i-1];
	for(register int i=1;i<=cnt;i++) sa[tong[l[i]]--]=i;
	for(register int i=cnt;i;i--)
	{
		int p=sa[i];
		size[link[p]]+=size[p];
		if(size[p]>1) ans=max(ans,1ll*size[p]*l[p]);
	}
	printf("%lld\n",ans);
	return 0;
}

应用

1.求本质不同的子串个数

1445 : 后缀自动机二·重复旋律5

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
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+10;
typedef long long ll;
char s[N];
int l[N<<1],link[N<<1],son[N<<1][26];
int cnt=1,last=1;
ll ans=0;

inline void ins(int s)
{
	int np=++cnt,p=last;
	last=np;l[np]=l[p]+1;
	for(;!son[p][s]&&p;p=link[p]) son[p][s]=np;
	if(!p) link[np]=1;
	else
	{
		int q=son[p][s];
		if(l[q]==l[p]+1) link[np]=q;
		else
		{
			int nq=++cnt;
			l[nq]=l[p]+1;
			memcpy(son[nq],son[q],sizeof(son[q]));
			link[nq]=link[q];link[q]=link[np]=nq;
			for(;son[p][s]==q;p=link[p]) son[p][s]=nq;
		}
	}
	ans+=1ll*(l[np]-l[link[np]]);
}

int main()
{
	scanf("%s",s);
	int n=strlen(s);
	for(register int i=0;i<n;i++) ins(s[i]-'a');
	printf("%lld\n",ans);
	return 0;
}

练习1：P4070 [SDOI2016]生成魔咒,与上一道实际上是同一道题。

练习2：P3975 [TJOI2015]弦论,将信息放在节点上，然后从根节点往下，每个点从’a’到’z’搜索。具体看代码。

练习一

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
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+100;
typedef long long ll;

ll ans; 
map<int,int> son[N<<1];
int l[N<<1],link[N<<1];
int cnt,last;

inline void ins(int s)
{
	int np=++cnt,p=last;
	last=np;l[np]=l[p]+1;
	for(;p&&!son[p][s];p=link[p]) son[p][s]=np;
	if(!p) link[np]=1;
	else
	{
		int q=son[p][s];
		if(l[q]==l[p]+1) link[np]=q;
		else
		{
			int nq=++cnt;
			l[nq]=l[p]+1;
			son[nq]=son[q];
			link[nq]=link[q];link[q]=link[np]=nq;
			for(;son[p][s]==q;p=link[p]) son[p][s]=nq;
		}
	}
	ans+=1ll*(l[np]-l[link[np]]);
}

int n;

int main()
{
	last=cnt=1;
	scanf("%d",&n);
	int x;
	for(register int i=1;i<=n;i++)
	{
		scanf("%d",&x);
		ins(x);
		printf("%lld\n",ans);
	}
	return 0;
}

练习二

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
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+1000;

char s[N];
int son[N][30],size[N],l[N],link[N];
int last,cnt;
int tong[N],sa[N];
int sum[N];

inline void ins(int s)
{
	int np=++cnt,p=last;
	last=np;l[np]=l[p]+1;
	size[np]=1;
	for(;p&&!son[p][s];p=link[p]) son[p][s]=np;
	if(!p) link[np]=1;
	else
	{
		int q=son[p][s];
		if(l[q]==l[p]+1) link[np]=q;
		else
		{
			int nq=++cnt;
			l[nq]=l[p]+1;
			memcpy(son[nq],son[q],sizeof(son[q]));
			link[nq]=link[q];link[q]=link[np]=nq;
			for(;son[p][s]==q;p=link[p]) son[p][s]=nq;
		}
	}
}

int opt,k,n;

int main()
{
	scanf("%s%d%d",s,&opt,&k);
	n=strlen(s);
	last=cnt=1;
	for(register int i=0;i<n;i++) ins(s[i]-'a');
	for(register int i=1;i<=cnt;i++) tong[l[i]]++;
	for(register int i=1;i<=cnt;i++) tong[i]+=tong[i-1];
	for(register int i=1;i<=cnt;i++) sa[tong[l[i]]--]=i;
	for(register int i=cnt;i;i--)
	{
		int p=sa[i];
		if(opt)
			size[link[p]]+=size[p];
		else 
			size[p]=1;
	}
	size[1]=0;
	for(register int i=cnt;i;i--)
	{
		int p=sa[i];
		sum[p]=size[p];
		for(register int j=0;j<26;j++)
		if(son[p][j]) sum[p]+=sum[son[p][j]];
	}
	if(k>sum[1])
	{
		puts("-1");
		return 0;
	}
	int x=1,p;
	while(k>0)
	{
		p=0;
		while(sum[son[x][p]]<k) k-=sum[son[x][p]],p++;
		x=son[x][p];
		putchar(p+'a');
		k-=size[x];
	}
	return 0;
}

2.求各子串出现的次数

1445 : 后缀自动机二·重复旋律5

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6+10;

char s[N];
int l[N<<1],link[N<<1],son[N<<1][30],size[N<<1];
int last=1,cnt=1;

inline void ins(int s)
{
	int np=++cnt,p=last;
	last=np;l[np]=l[p]+1;
	for(;p&&!son[p][s];p=link[p]) son[p][s]=np;
	if(!p) link[np]=1;
	else
	{
		int q=son[p][s];
		if(l[q]==l[p]+1) link[np]=q;
		else
		{
			int nq=++cnt;
			l[nq]=l[p]+1;
			memcpy(son[nq],son[q],sizeof(son[q]));
			link[nq]=link[q],link[q]=link[np]=nq;
			for(;son[p][s]==q;p=link[p]) son[p][s]=nq;
		}
	}
	size[np]=1;
}

int tong[N<<1],sa[N<<1];
int ans[N],n;

int main()
{
	scanf("%s",s);
	n=strlen(s);
	for(register int i=0;i<n;i++) ins(s[i]-'a');
	for(register int i=1;i<=cnt;i++) tong[l[i]]++;
	for(register int i=1;i<=cnt;i++) tong[i]+=tong[i-1];
	for(register int i=1;i<=cnt;i++) sa[tong[l[i]]--]=i;
	for(register int i=cnt;i;i--)
	{
		int p=sa[i];
		size[link[p]]+=size[p];
		ans[l[p]]=max(ans[l[p]],size[p]);
	}
 	for(register int i=n-1;i;i--) ans[i]=max(ans[i],ans[i+1]);
	for(register int i=1;i<=n;i++) printf("%d\n",ans[i]);
	return 0;
}

在建完后缀自动机后， 可以先用桶排序将所有节点的长度进行排序，按倒序更新每个节点的size，但是这个size只是以当前节点为结尾的最长子串的出现次数，并没有更新它的后缀的出现次数；

这时就需要用到一个结论：长度小的子串出现的次数大于等于比它长的子串出现的次数。

然后只需在最后将ans与后一个取一个max即可。

3.求多个串之间的信息

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

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
#include<bits/stdc++.h>
using namespace std;
const int N = 510000;
char s[300000];
int son[N][26],fa[N];
int l[N],last=1,cnt=1;

inline void ins(int s)
{
	int np=++cnt,p=last;
	last=np;l[np]=l[p]+1;
	for(;!son[p][s]&&p;p=fa[p]) son[p][s]=np;
	if(!p) fa[np]=1;
	else
	{
		int q=son[p][s];
		if(l[q]==l[p]+1) fa[np]=q;
		else
		{
			int nq=++cnt;
			l[nq]=l[p]+1;
			memcpy(son[nq],son[q],sizeof(son[q]));
			fa[nq]=fa[q];fa[q]=fa[np]=nq;
			for(;son[p][s]==q;p=fa[p]) son[p][s]=nq;
		}
	}
	return;
}

inline void work()
{
	int n=strlen(s),p=1,len=0,c,ans=0;
	for(register int i=0;i<n;i++)
	{
		c=(int)(s[i]-'a');
		if(son[p][c]) len++,p=son[p][c];
		else
		{
			for(;p&&!son[p][c];p=fa[p]);
			if(p) len=l[p]+1,p=son[p][c];
			else p=1,len=0;
		}
		ans=max(ans,len);
	}
	printf("%d\n",ans);
	return;
}

int main()
{
	scanf("%s",s);
	int n=strlen(s);
	for(register int i=0;i<n;i++) ins((int)(s[i]-'a'));
	scanf("%s",s);
	work();
	return 0;
}

将每个字符串之间用’:’连接成一个字符串并建立Sam，有一个显然的结论：对于一个节点（状态），能到达它的路径个数便是该节点（状态）中子串的个数。对于这道题我们特判一下，不遍历为’:’的边，因为一个字串的后缀和另一个字串的前缀组成的子串必定包含’:’。

练习：求n个字符串中本质不同的子串。

题解：同上，用’:’连接字符串统计即可。

4.求LCS（字符串匹配）

SP1811 LCS - Longest Common Substring

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
#include<bits/stdc++.h>
using namespace std;
const int N = 510000;
char s[300000];
int son[N][26],fa[N];
int l[N],last=1,cnt=1;

inline void ins(int s)
{
	int np=++cnt,p=last;
	last=np;l[np]=l[p]+1;
	for(;!son[p][s]&&p;p=fa[p]) son[p][s]=np;
	if(!p) fa[np]=1;
	else
	{
		int q=son[p][s];
		if(l[q]==l[p]+1) fa[np]=q;
		else
		{
			int nq=++cnt;
			l[nq]=l[p]+1;
			memcpy(son[nq],son[q],sizeof(son[q]));
			fa[nq]=fa[q];fa[q]=fa[np]=nq;
			for(;son[p][s]==q;p=fa[p]) son[p][s]=nq;
		}
	}
	return;
}

inline void work()
{
	int n=strlen(s),p=1,len=0,c,ans=0;
	for(register int i=0;i<n;i++)
	{
		c=(int)(s[i]-'a');
		if(son[p][c]) len++,p=son[p][c];
		else
		{
			for(;p&&!son[p][c];p=fa[p]);
			if(p) len=l[p]+1,p=son[p][c];
			else p=1,len=0;
		}
		ans=max(ans,len);
	}
	printf("%d\n",ans);
	return;
}

int main()
{
	scanf("%s",s);
	int n=strlen(s);
	for(register int i=0;i<n;i++) ins((int)(s[i]-'a'));
	scanf("%s",s);
	work();
	return 0;
}
本文作者： syrsteven
最后更新： 2023年09月02日 04:06:21
本文链接： http://syrsteven.github.io/post/b1c0144b.html
版权声明： 本作品采用 CC BY-NC-SA 4.0 许可协议进行许可，转载请注明出处！

扫一扫，分享到微信

微信分享二维码

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

    			  jsonContent:
				meta: false
				pages: false
				posts:
				  title: true
				  date: true
				  path: true
				  text: false
				  raw: false
				  content: false
				  slug: false
				  updated: false
				  comments: false
				  link: false
				  permalink: false
				  excerpt: false
				  categories: false
				  tags: true


There's nothing