[字符串]

来自csy课件的一些字符串题

KMP

HNOI2008 GT考试

NOI2014 动物园

Description

设 numinum_i 为前缀 ii 所拥有的,与其相同⻓度后缀相等且不相交的的前缀个数。

TT 组询问,每组询问给出一字符串,求 ∏(numi+1)\prod (num_i + 1)

T≤5,∣S∣≤106T \le5, |S| \le 10^6

Solution

[KMP]

KMP又快忘光了。。。

求出fail数组后倍增，跳到小于等于i2\frac{i}{2}的位置，加上深度的贡献

HNOI2019 JOJO

大致思路是：

  • 通过离线dfs处理强制在线
  • 通过把连续的字符缩成一个字段，解决字符数量太多的问题
  • 利用border只要大于串长的一半就一定会出现循环，且若干个循环只有最后两个循环节才可能产生贡献的性质，使得KMP的复杂度不再是均摊，而是log\log（每次长度至少会减半）

感觉还没完全把细节想清楚，先咕咕咕，贴一下csy的标程

Code 
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 <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <vector>
using namespace std;
const int Max_n = 1e5 + 5, mod = 998244353;
int n;
long long Ans[Max_n];
int fail[Max_n], l[Max_n], len[Max_n], sum[Max_n];
char P[Max_n], c[Max_n];
int cntr, hd[Max_n], nx[Max_n], to[Max_n];
void addr(int u, int v)
{
	cntr++;
	nx[cntr] = hd[u], to[cntr] = v;
	hd[u] = cntr;
}
void Mod(long long &x) { x %= mod; }

void calc(int x, int L, long long ans)
{
	if (len[x])
	{
		if (!L) Mod(ans = (len[x] - 1) * len[x] / 2);
		int maxx = 0, now = fail[L], lastgap = 0;
		for (int i = fail[L]; ~i; i = fail[i]) // 算答案 
		{
			if (P[i + 1] == c[x] && min(l[i + 1], len[x]) > maxx)
			{
				int tp = maxx;
				maxx = min(l[i + 1], len[x]);
				Mod(ans +=
						1ll * (maxx - tp) * sum[i] + (maxx - tp) * (tp + 1 + maxx) / 2);
			}
			if ((i - fail[i] == lastgap) && i) i = i % lastgap + lastgap;
			lastgap = i - fail[i];
		}
		if (c[x] == P[1] && L) Mod(ans += (len[x] - maxx) * l[1]);
		lastgap = 0;
		fail[L + 1] = 0;
		for (int i = fail[L++]; ~i; i = fail[i]) // 加入KMP
		{
			if (P[1] == c[x] && l[1] <= len[x]) fail[L] = 1;
			if (P[i + 1] == c[x] && l[i + 1] == len[x])
			{
				fail[L] = i + 1;
				break;
			}
			if (i - fail[i] == lastgap && i) i = i % lastgap + lastgap;
			lastgap = i - fail[i];
		}
		P[L] = c[x], sum[L] = sum[L - 1] + (l[L] = len[x]);
	}
	Ans[x] = ans;
	for (int i = hd[x]; i; i = nx[i]) calc(to[i], L, ans);
}
int main()
{
#ifndef ONLINE_JUDGE
	freopen("5287.in", "r", stdin);
	freopen("5287.out", "w", stdout);
#endif
	scanf("%d", &n);
	int opt, x;
	for (int i = 1; i <= n; i++)
	{
		scanf("%d%d", &opt, &x);
		if (opt == 2) addr(x, i);
		else
		{
			addr(i - 1, i);
			scanf(" %c", &c[i]);
			len[i] = x;
		}
	}
	fail[0] = -1;
	calc(0, 0, 0);
	for (int i = 1; i <= n; i++) printf("%lld\n", Ans[i]);
}

AC自动机

「NOI2011」阿狸的打字机

Description

有一空串,接下来有 nn 个操作,一是在串尾加入小写字母,二是将当前串记录,三是删除当前串末尾字母。

接下来 mm 个询问,每次询问第 xx 个记录的串在第 yy 个记录的串中出现了多少次。

n,m≤105n, m\le 10^5

Solution

[Trie] [AC自动机] [树状数组]

加入/记录/删除都可以在trie上实现

如何求xx在yy中出现了多少次？

暴力做法：建出AC自动机后，把yy放到AC自动机上跑，对于经过的每个节点，看它不断跳fail时能否跳到xx所在节点

发现就是问fail树上，xx的子树里有多少个节点是yy到根路径（trie路径）上的节点，显然子树的限制可以树状数组搞

离线询问，把询问挂在yy上。dfs整棵trie，访问一个点就在树状数组++，出去的时候--。这样的话，到这个点的时候树状数组里就只有它到根路径上的信息了，直接查询即可

POI 2000 病毒

Description

有 nn 个 01 串,问是否能构造出无限⻓的文本串使得任意一个 01 串都不为此串的子串。

设 lenlen 为 nn 个 01 串的⻓度之和。

n≤2000,len≤30000n\le 2000, len\le 30000

Solution

[AC自动机]

把AC自动机全建出来（建出trie图）后，就是要在上面找到一个环，使得它不包含任何一个给出的0101串

也就是说，给定的0101串的结尾位置都不能走，并且如果某个节点的fail链上存在给定串的结尾标记，那么也不能走

JSOI2007 文本生成器

Description

给出 nn 个模式串,皆有由大写字母组成。问有多少种由大写字母组成的,⻓度为 mm 的文本串满足其中至少有一 个模式串。模式串不会超过 mm

n≤60,m≤100n\le 60, m\le 100

Solution

[AC自动机]

补集转化，总方案减去不含模式串的情况。设fi,jf_{i, j}表示在AC自动机上到ii号节点，长度为jj且不含模式串的方案数。直接转移

注意到AC自动机（实际是trie图）上可能会存在环，不过并不影响dp，因为长度是有限的。。。

CF 86C

Description

给出 mm 个模式串 ss,问有多少种⻓度为n n 的字符串,使得对于任意一个位置 ii ,都满足存在一个区间 l≤i≤rl \le i \le r,使得这段区间代表的子串与某一个模式串相等

n≤1000,m≤10,∣s∣≤10n\le 1000, m\le 10, |s| \le 10

Solution

[AC自动机]

AC自动机上dp

设fx,i,lenf_{x, i, len}表示走到xx节点，构造到第ii位，结尾有lenlen个字符不合法（没有模式串与它们匹配）的方案数，倒着dp

预处理maxlenxmaxlen_x，表示xx节点所有后缀最长的那个可匹配的串的长度（这可以在build_fail时求出）

枚举AC自动机上节点yy，若maxleny≥len+1maxlen_y \ge len + 1，则可以从fy,i+1,0f_{y, i + 1, 0}转移过来；否则从fy,i+1,len+1f_{y, i + 1, len + 1}转移过来

有很多无用状态，记忆化搜索即可