AC自动机 (Aho–Corasick algorithm)

如何建树

AC自动机可以被补全成Trie图。

好处是不用每次跳Fail指针

\href{https://wenku.baidu.com/view/9df73e3567ec102de2bd89ae.html}{论文一}

\href{https://wenku.baidu.com/view/e0cc22d3240c844769eaeeac.html}{论文二}

\href{https://blog.csdn.net/thy_asdf/article/details/47082915}{正确的AC自动机写法。}

Fail Tree

自己孩子节点的 Fail 指针 = 自己Fail指针节点的孩子

对于每个节点，找到最长的后缀，在Trie中出现过（如果只有一个串，等价于KMP算法）

Fail 指针
一定是从长度长的节点指向长度短的节点
每一个点只有一个Fail指针（最长的）
所有Fail指针构成一棵树

Fail指针直接指向的是最长的在Trie中出现过的后缀
如果想找到所有在Trie中出现过的后缀
那么只需要沿着Fail指针不断的向上跳

AC自动机 / TRIE图

扩展KMP的应用
AC自动机

参考题目

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

https://www.luogu.com.cn/problem/P3796

题目描述

有 $N$ 个由小写字母组成的模式串以及一个文本串 $T$ 。每个模式串可能会在文本串中出现多次。你需要找出哪些模式串在文本串 $T$ 中出现的次数最多。

输入格式

输入含多组数据。保证输入数据不超过 $50$ 组。

每组数据的第一行为一个正整数 $N$ ，表示共有 $N$ 个模式串， $1 \leq N \leq 150$ 。

接下去 $N$ 行，每行一个长度小于等于 $70$ 的模式串。下一行是一个长度小于等于 $10^6$ 的文本串 $T$ 。保证不存在两个相同的模式串。

输入结束标志为 $N=0$ 。

输出格式

对于每组数据，第一行输出模式串最多出现的次数，接下去若干行每行输出一个出现次数最多的模式串，按输入顺序排列。

样例 #1

样例输入 #1

2
aba
bab
ababababac
6
beta
alpha
haha
delta
dede
tata
dedeltalphahahahototatalpha
0

样例输出 #1

4
aba
2
alpha
haha

提示

参考代码

#include <bits/stdc++.h>
using namespace std;
int n;
int t[200020][26], tt;
int f[200020];
int s[200020];
int a[200020];
int q[200020], qq;
char c[200][80];
char o[1000080];
int ins(char *s)
{
	int p = 0;
	for (; *s; s++)
	{
		if (t[p][*s - 'a'] == 0)
		{
			t[p][*s - 'a'] = ++tt;
		}
		p = t[p][*s - 'a'];
	}
	return p;
}
int main()
{
	while (true)
	{
		scanf("%d", &n);
		if (n == 0)
		{
			break;
		}
		tt = 0;
		memset(t, 0, sizeof t);
		memset(f, 0, sizeof f);
		memset(s, 0, sizeof s);
		for (int i = 0; i < n; i++)
		{
			scanf("%s", c[i]);
			a[i] = ins(c[i]);
		}
		qq = 0;
		q[qq++] = 0;
		for (int j = 0; j < qq; j++)
		{
			int u = q[j];
			for (int i = 0; i < 26; i++)
			{
				if (t[u][i])
				{
					f[t[u][i]] = u ? t[f[u]][i] : 0;
					q[qq++] = t[u][i];
				}
				else
				{
					t[u][i] = t[f[u]][i];
				}
			}
		}
		scanf("%s", o);
		for (int p = 0, i = 0; o[i]; i++)
		{
			p = t[p][o[i] - 'a'];
			s[p]++;
		}
		for (int i = tt; i > 0; i--)
		{
			s[f[q[i]]] += s[q[i]];
		}
		int mx = 0, cnt = 0;
		for (int i = 0; i < n; i++)
		{
			if (mx < s[a[i]])
			{
				mx = s[a[i]];
				cnt = 1;
			}
			else if (mx == s[a[i]])
			{
				cnt++;
			}
		}
		printf("%d\n", mx);
		for (int i = 0; i < n; i++)
		{
			if (mx == s[a[i]])
			{
				printf("%s\n", c[i]);
			}
		}
	}
	return 0;
}

题解

P3808 【模板】AC 自动机（简单版）

https://www.luogu.com.cn/problem/P3808

题目背景

警告：通过套取数据而直接“打表”过题者，是作弊行为，发现即棕名。

这是一道简单的 AC 自动机模板题，用于检测正确性以及算法常数。

题目描述

给定 $n$ 个模式串 $s_i$ 和一个文本串 $t$ ，求有多少个不同的模式串在文本串里出现过。
两个模式串不同当且仅当他们编号不同。

输入格式

第一行是一个整数，表示模式串的个数 $n$ 。
第 $2$ 到第 $(n + 1)$ 行，每行一个字符串，第 $(i + 1)$ 行的字符串表示编号为 $i$ 的模式串 $s_i$ 。
最后一行是一个字符串，表示文本串 $t$ 。

输出格式

输出一行一个整数表示答案。

样例 #1

样例输入 #1

3
a
aa
aa
aaa

样例输出 #1

样例 #2

样例输入 #2

4
a
ab
ac
abc
abcd

样例输出 #2

样例 #3

样例输入 #3

2
a
aa
aa

样例输出 #3

提示

样例 1 解释

$s_2$ 与 $s_3$ 编号（下标）不同，因此各自对答案产生了一次贡献。

样例 2 解释

$s_1$ ， $s_2$ ， $s_4$ 都在串 abcd 里出现过。

数据规模与约定

对于 $50\%$ 的数据，保证 $n = 1$ 。
对于 $100\%$ 的数据，保证 $1 \leq n \leq 10^6$ ， $1 \leq |t| \leq 10^6$ ， $1 \leq \sum\limits_{i = 1}^n |s_i| \leq 10^6$ 。 $s_i, t$ 中仅包含小写字母。

参考代码

#include <bits/stdc++.h>
using namespace std;
int n;
int t[1000020][26], tt;
int f[1000020];
int s[1000020];
int a[1000020];
int q[1000020], qq;
char c[2000020];
int ins(char *s)
{
	int p = 0;
	for (; *s; s++)
	{
		if (t[p][*s - 'a'] == 0)
		{
			t[p][*s - 'a'] = ++tt;
		}
		p = t[p][*s - 'a'];
	}
	return p;
}
int main()
{
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
	{
		scanf("%s", c);
		a[i] = ins(c);
	}
	q[qq++] = 0;
	for (int j = 0; j < qq; j++)
	{
		int u = q[j];
		for (int i = 0; i < 26; i++)
		{
			if (t[u][i])
			{
				f[t[u][i]] = u ? t[f[u]][i] : 0;
				q[qq++] = t[u][i];
			}
			else
			{
				t[u][i] = t[f[u]][i];
			}
		}
	}
	scanf("%s", c);
	for (int p = 0, i = 0; c[i]; i++)
	{
		p = t[p][c[i] - 'a'];
		s[p]++;
	}
	for (int i = tt; i > 0; i--)
	{
		s[f[q[i]]] += s[q[i]];
	}
	int z = 0;
	for (int i = 0; i < n; i++)
	{
		z += s[a[i]] > 0;
	}
	printf("%d\n", z);
	return 0;
}

题解

P5357 【模板】AC 自动机（二次加强版）

https://www.luogu.com.cn/problem/P5357

题目描述

给你一个文本串 $S$ 和 $n$ 个模式串 $T_{1 \sim n}$ ，请你分别求出每个模式串 $T_i$ 在 $S$ 中出现的次数。

输入格式

第一行包含一个正整数 $n$ 表示模式串的个数。

接下来 $n$ 行，第 $i$ 行包含一个由小写英文字母构成的非空字符串 $T_i$ 。

最后一行包含一个由小写英文字母构成的非空字符串 $S$ 。

数据不保证任意两个模式串不相同。

输出格式

输出包含 $n$ 行，其中第 $i$ 行包含一个非负整数表示 $T_i$ 在 $S$ 中出现的次数。

样例 #1

样例输入 #1

5
a
bb
aa
abaa
abaaa
abaaabaa

样例输出 #1

提示

对于 $100 \%$ 的数据， $1 \le n \le 2 \times {10}^5$ ， $T_{1 \sim n}$ 的长度总和不超过 $2 \times {10}^5$ ， $S$ 的长度不超过 $2 \times {10}^6$ 。

参考代码

#include <bits/stdc++.h>
using namespace std;
int n;
int t[200020][26], tt;
int f[200020];
int s[200020];
int a[200020];
int q[200020], qq;
char c[2000020];
int ins(char *s)
{
	int p = 0;
	for (; *s; s++)
	{
		if (t[p][*s - 'a'] == 0)
		{
			t[p][*s - 'a'] = ++tt;
		}
		p = t[p][*s - 'a'];
	}
	return p;
}
int main()
{
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
	{
		scanf("%s", c);
		a[i] = ins(c);
	}
	q[qq++] = 0;
	for (int j = 0; j < qq; j++)
	{
		int u = q[j];
		for (int i = 0; i < 26; i++)
		{
			if (t[u][i])
			{
				f[t[u][i]] = u ? t[f[u]][i] : 0;
				q[qq++] = t[u][i];
			}
			else
			{
				t[u][i] = t[f[u]][i];
			}
		}
	}
	scanf("%s", c);
	for (int p = 0, i = 0; c[i]; i++)
	{
		p = t[p][c[i] - 'a'];
		s[p]++;
	}
	for (int i = tt; i > 0; i--)
	{
		s[f[q[i]]] += s[q[i]];
	}
	for (int i = 0; i < n; i++)
	{
		printf("%d\n", s[a[i]]);
	}
	return 0;
}

题解

P4052 [JSOI2007]文本生成器

https://www.luogu.com.cn/problem/P4052

题目描述

JSOI 交给队员 ZYX 一个任务，编制一个称之为“文本生成器”的电脑软件：该软件的使用者是一些低幼人群，他们现在使用的是 GW 文本生成器 v6 版。

该软件可以随机生成一些文章——总是生成一篇长度固定且完全随机的文章。也就是说，生成的文章中每个字符都是完全随机的。如果一篇文章中至少包含使用者们了解的一个单词，那么我们说这篇文章是可读的（我们称文章 $s$ 包含单词 $t$ ，当且仅当单词 $t$ 是文章 $s$ 的子串）。但是，即使按照这样的标准，使用者现在使用的 GW 文本生成器 v6 版所生成的文章也是几乎完全不可读的。ZYX 需要指出 GW 文本生成器 v6 生成的所有文本中，可读文本的数量，以便能够成功获得 v7 更新版。你能帮助他吗？

答案对 $10^4 + 7$ 取模。

输入格式

第一行有两个整数，分别表示使用者了解的单词总数 $n$ 和生成的文章长度 $m$ 。

接下来 $n$ 行，每行一个字符串 $s_i$ ，表示一个使用者了解的单词。

输出格式

输出一行一个整数表示答案对 $10^4 + 7$ 取模的结果。

样例 #1

样例输入 #1

2 2
A
B

样例输出 #1

提示

数据规模与约定

对于全部的测试点，保证：

$1 \leq n \leq 60$ ， $1 \leq m \leq 100$ 。
$1 \leq |s_i| \leq 100$ ，其中 $|s_i|$ 表示字符串 $s_i$ 的长度。
$s_i$ 中只含大写英文字母。

参考代码

#include <bits/stdc++.h>
using namespace std;
const int mod = 10007;
int n, m;
int t[6020][26], tt;
int f[120][6020];
int v[6020];
int g[6020];
int q[6020], qq;
char c[120];
void ins(char *s)
{
	int p = 0;
	for (; *s; s++)
	{
		if (t[p][*s - 'A'] == 0)
		{
			t[p][*s - 'A'] = ++tt;
		}
		p = t[p][*s - 'A'];
	}
	v[p] = 1;
}
int main()
{
	scanf("%d%d", &n, &m);
	for (int i = 0; i < n; i++)
	{
		scanf("%s", c);
		ins(c);
	}
	q[qq++] = 0;
	for (int j = 0; j < qq; j++)
	{
		int u = q[j];
		v[u] |= v[g[u]];
		for (int i = 0; i < 26; i++)
		{
			if (t[u][i])
			{
				g[t[u][i]] = u ? t[g[u]][i] : 0;
				q[qq++] = t[u][i];
			}
			else
			{
				t[u][i] = t[g[u]][i];
			}
		}
	}
	f[0][0] = 1;
	int z = 1;
	for (int i = 0; i < m; i++)
	{
		z = z * 26 % mod;
		for (int j = 0; j <= tt; j++)
		{
			for (int k = 0; k < 26; k++)
			{
				if (!v[t[j][k]])
				{
					f[i + 1][t[j][k]] = (f[i + 1][t[j][k]] + f[i][j]) % mod;
				}
			}
		}
	}
	for (int j = 0; j <= tt; j++)
	{
		z = (z + mod - f[m][j]) % mod;
	}
	printf("%d\n", z);
	return 0;
}

题解

P4045 [JSOI2009] 密码

https://www.luogu.com.cn/problem/P4045

题目描述

众所周知，密码在信息领域起到了不可估量的作用。对于普通的登陆口令以，唯一的破解方法就是暴力破解——逐个尝试所有可能的字母组合，但这是一项很耗时又容易被发现的工作。所以，为了获取对方的登陆口令，在暴力破解密码之前，必须先做大量的准备工作。经过情报的搜集，现在得到了若干有用信息，形如：

“我观察到，密码中含有字符串*。”

例如，对于一个 $10$ 位的密码以及观察到的字符串 hello 与 world，可能的密码组合为 helloworld与 worldhello；而对于 $6$ 位的密码以及到的字符串 good 与 day,可能的密码组合为 gooday。

有了这些信息，就能够大大地减少尝试的次数了。请编一个程序，计算所有密码组合的可能。密码中仅可能包含 a-z 之间的小写字母。

输入格式

输入数据首先输入两个整数 $L,N$ ，分别表示密码的长度与观察到子串的个数。

接下来 $N$ 行，每行若干个字符，描述了每个观察到的字符串。

输出格式

输出数据第一行为一个整数，代表了满足所有观察条件字符串的总数。

若这个数字小于等于 $42$ ，则按字典顺序输出所有密码的可能情况，每行一个，否则，只输出满足所有观察条件字符串的总数即可。

样例 #1

样例输入 #1

10 2
hello
world

样例输出 #1

2
helloworld
worldhello

提示

对于 $100\%$ 的数据， $1\leq L\leq 25,1\leq N\leq 10$ ，每个观察到的字符串长不超过 $10$ ，并且保证输出结果小于 $2^{63}$ 。

参考代码

题解

P3041 [USACO12JAN]Video Game G

https://www.luogu.com.cn/problem/P3041

题目描述

Bessie 在玩一款游戏，该游戏只有三个技能键 A，B，C 可用，但这些键可用形成 $n$ 种特定的组合技。第 $i$ 个组合技用一个字符串 $s_i$ 表示。

Bessie 会输入一个长度为 $k$ 的字符串 $t$ ，而一个组合技每在 $t$ 中出现一次，Bessie 就会获得一分。 $s_i$ 在 $t$ 中出现一次指的是 $s_i$ 是 $t$ 从某个位置起的连续子串。如果 $s_i$ 从 $t$ 的多个位置起都是连续子串，那么算作 $s_i$ 出现了多次。

若 Bessie 输入了恰好 $k$ 个字符，则她最多能获得多少分？

输入格式

输入的第一行是两个整数，分别表示组合技个数 $n$ 和 Bessie 输入的字符数 $k$ 。

接下来 $n$ 行，每行一个字符串 $s_i$ ，表示一种组合技。

输出格式

输出一行一个整数表示答案。

样例 #1

样例输入 #1

3 7 
ABA 
CB 
ABACB

样例输出 #1

提示

样例 1 解释

Bessie 如果输入 ABACBCB，则 ABA 出现了一次，ABACB 出现了一次，CB 出现了两次，共得到 $4$ 分。可以证明这是最优的输入。

数据规模与约定

对于全部的测试点，保证：

$1 \leq n \leq 20$ ， $1 \leq k \leq 10^3$ 。
$1 \leq |s_i| \leq 15$ 。其中 $|s_i|$ 表示字符串 $s_i$ 的长度。
$s$ 中只含大写字母 A，B，C。

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, m;
int t[320][26], tt;
int f[1020][320];
int v[320];
int g[320];
int q[320], qq;
char c[20];
void ins(char *s)
{
	int p = 0;
	for (; *s; s++)
	{
		if (t[p][*s - 'A'] == 0)
		{
			t[p][*s - 'A'] = ++tt;
		}
		p = t[p][*s - 'A'];
	}
	v[p]++;
}
int main()
{
	scanf("%d%d", &n, &m);
	for (int i = 0; i < n; i++)
	{
		scanf("%s", c);
		ins(c);
	}
	q[qq++] = 0;
	for (int j = 0; j < qq; j++)
	{
		int u = q[j];
		v[u] += v[g[u]];
		for (int i = 0; i < 26; i++)
		{
			if (t[u][i])
			{
				g[t[u][i]] = u ? t[g[u]][i] : 0;
				q[qq++] = t[u][i];
			}
			else
			{
				t[u][i] = t[g[u]][i];
			}
		}
	}
	memset(f, 0xc0, sizeof f);
	f[0][0] = 0;
	for (int i = 0; i < m; i++)
	{
		for (int j = 0; j <= tt; j++)
		{
			for (int k = 0; k < 26; k++)
			{
				f[i + 1][t[j][k]] = max(f[i + 1][t[j][k]], f[i][j] + v[t[j][k]]);
			}
		}
	}
	int z = 0;
	for (int j = 0; j <= tt; j++)
	{
		z = max(z, f[m][j]);
	}
	printf("%d\n", z);
	return 0;
}

题解

P3121 [USACO15FEB]Censoring G

https://www.luogu.com.cn/problem/P3121

题目描述

FJ 把杂志上所有的文章摘抄了下来并把它变成了一个长度不超过 $10^5$ 的字符串 $s$ 。他有一个包含 $n$ 个单词的列表，列表里的 $n$ 个单词记为 $t_1 \cdots t_n$ 。他希望从 $s$ 中删除这些单词。

FJ 每次在 $s$ 中找到最早出现的列表中的单词（最早出现指该单词的开始位置最小），然后从 $s$ 中删除这个单词。他重复这个操作直到 $s$ 中没有列表里的单词为止。注意删除一个单词后可能会导致 $s$ 中出现另一个列表中的单词。

FJ 注意到列表中的单词不会出现一个单词是另一个单词子串的情况，这意味着每个列表中的单词在 $s$ 中出现的开始位置是互不相同的。

请帮助 FJ 完成这些操作并输出最后的 $s$ 。

输入格式

第一行是一个字符串，表示文章 $s$ 。

第二行有一个整数，表示单词列表的单词个数 $n$ 。

第 $3$ 到第 $(n + 2)$ 行，每行一个字符串，第 $(i + 2)$ 行的字符串 $t_i$ 表示第 $i$ 个单词。

输出格式

输出一行一个字符串，表示操作结束后的 $s$ 。

样例 #1

样例输入 #1

begintheescapexecutionatthebreakofdawn 
2 
escape 
execution

样例输出 #1

beginthatthebreakofdawn

提示

数据规模与约定

对于全部的测试点，保证：

$1 \leq |s|, \sum\limits_{i = 1}^n |t_i|, n \leq 10^5$ 。
字符串均只含小写字母。
操作结束后 $s$ 不会被删成空串。
对于所有的 $i \neq j$ ， $t_i$ 不是 $t_j$ 的子串。

其中对于一个字符串 $x$ ，约定 $|x|$ 表示 $x$ 的长度。

提示

操作过程中 $s$ 有可能某一个前缀子串被完全删除，请格外注意这一点。

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, m;
int t[200020][26], tt;
int f[200020];
int s[200020];
int v[200020];
int a[200020];
int q[200020], qq;
char o[2000020];
char c[2000020];
void ins(char *s)
{
	int p = 0, l = strlen(s);
	for (; *s; s++)
	{
		if (t[p][*s - 'a'] == 0)
		{
			t[p][*s - 'a'] = ++tt;
		}
		p = t[p][*s - 'a'];
	}
	v[p] = l;
}
int main()
{
	scanf("%s", o);
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
	{
		scanf("%s", c);
		ins(c);
	}
	q[qq++] = 0;
	for (int j = 0; j < qq; j++)
	{
		int u = q[j];
		v[u] |= v[f[u]];
		for (int i = 0; i < 26; i++)
		{
			if (t[u][i])
			{
				f[t[u][i]] = u ? t[f[u]][i] : 0;
				q[qq++] = t[u][i];
			}
			else
			{
				t[u][i] = t[f[u]][i];
			}
		}
	}
	for (int p = 0, i = 0; o[i]; i++)
	{
		p = t[p][o[i] - 'a'];
		o[m++] = o[i];
		if (v[p])
		{
			m -= v[p];
			p = a[m];
		}
		else
		{
			a[m] = p;
		}
	}
	o[m] = 0;
	printf("%s\n", o);
	return 0;
}

题解

P2444 [POI2000]病毒

https://www.luogu.com.cn/problem/P2444

题目描述

二进制病毒审查委员会最近发现了如下的规律：某些确定的二进制串是病毒的代码。如果某段代码中不存在任何一段病毒代码，那么我们就称这段代码是安全的。现在委员会已经找出了所有的病毒代码段，试问，是否存在一个无限长的安全的二进制代码。

示例：

例如如果 $\{011, 11, 00000\}$ 为病毒代码段，那么一个可能的无限长安全代码就是 $010101 \ldots$ 。如果 $\{01, 11, 000000\}$ 为病毒代码段，那么就不存在一个无限长的安全代码。

现在给出所有的病毒代码段，判断是否存在无限长的安全代码。

输入格式

第一行包括一个整数 $n$ ，表示病毒代码段的数目。

以下的 $n$ 行每一行都包括一个非空的 $01$ 字符串，代表一个病毒代码段。

输出格式

如果存在无限长的安全代码，输出 TAK，否则输出 NIE。

样例 #1

样例输入 #1

样例输出 #1

NIE

提示

$1 \leq n \leq 2000$ ，所有病毒代码段的总长度不超过 $3 \times 10^4$ 。

参考代码

#include <bits/stdc++.h>
using namespace std;
int n;
int t[30020][2], tt;
int v[30020];
int g[30020];
int q[30020], qq;
int in[30020];
char c[30020];
void ins(char *s)
{
	int p = 0;
	for (; *s; s++)
	{
		if (t[p][*s - '0'] == 0)
		{
			t[p][*s - '0'] = ++tt;
		}
		p = t[p][*s - '0'];
	}
	v[p] = 1;
}
bool dfs(int x)
{
	if (v[x])
	{
		return v[x] == 2;
	}
	v[x] = 2;
	if (dfs(t[x][0]) || dfs(t[x][1]))
	{
		return true;
	}
	v[x] = 1;
	return false;
}
int main()
{
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
	{
		scanf("%s", c);
		ins(c);
	}
	q[qq++] = 0;
	for (int j = 0; j < qq; j++)
	{
		int u = q[j];
		v[u] |= v[g[u]];
		for (int i = 0; i < 2; i++)
		{
			if (t[u][i])
			{
				g[t[u][i]] = u ? t[g[u]][i] : 0;
				q[qq++] = t[u][i];
			}
			else
			{
				t[u][i] = t[g[u]][i];
			}
		}
	}
	for (int i = 0; i <= tt; i++)
	{
		for (int j = 0; j < 26; j++)
		{
			in[t[i][j]]++;
		}
	}
	puts(dfs(0) ? "TAK" : "NIE");
	return 0;
}

题解

P5840 [COCI2015]Divljak

https://www.luogu.com.cn/problem/P5840

题目描述

Alice 有 $n$ 个字符串 $\mathrm{S}_1, \mathrm{S}_2, \ldots, \mathrm{S}_n$ ，Bob 有一个字符串集合 $\mathrm{T}$ ，一开始集合是空的。

接下来会发生 $q$ 个操作，操作有两种形式：

1 P：Bob 往自己的集合里添加了一个字符串 $\mathrm{P}$ 。
2 x：Alice 询问 Bob，集合 $\mathrm{T}$ 中有多少个字符串包含串 $\mathrm{S}_x$ （我们称串 $\mathrm{A}$ 包含串 $\mathrm{B}$ ，当且仅当 $\mathrm{B}$ 是 $\mathrm{A}$ 的子串）。

输入格式

第一行一个整数 $n$ 。

接下来 $n$ 行，第 $i$ 行一个字符串 $\mathrm{S}_i$ 。

接下来一行一个整数 $q$ 。

接下来 $q$ 行，每行一个操作。

输出格式

对每个 2 x 操作，一行一个整数，表示答案。

样例 #1

样例输入 #1

3
a
bc
abc
5
1 abca
2 1
1 bca
2 2
2 3

样例输出 #1

1
2
1

提示

对于 $100\%$ 的数据， $1 \leq n,q \leq 10^5$ ，字符串由小写字母构成，所有字符串的总长 $\le 2 \times 10^6$ 。

参考代码

题解

P3311 [SDOI2014] 数数

https://www.luogu.com.cn/problem/P3311

题目描述

我们称一个正整数 $x$ 是幸运数，当且仅当它的十进制表示中不包含数字串集合 $s$ 中任意一个元素作为其子串。例如当 $s = \{22, 333, 0233\}$ 时， $233$ 是幸运数， $2333$ 、 $20233$ 、 $3223$ 不是幸运数。给定 $n$ 和 $s$ ，计算不大于 $n$ 的幸运数个数。

答案对 $10^9 + 7$ 取模。

输入格式

第一行有一个整数，表示 $n$ 。

第二行有一个整数，表示 $s$ 中的元素个数 $m$ 。

接下来 $m$ 行，每行一个数字串 $s_i$ ，表示 $s$ 中的一个元素。

输出格式

输出一行一个整数，表示答案对 $10^9 + 7$ 取模的结果。

样例 #1

样例输入 #1

样例输出 #1

提示

样例 1 解释

除了 $3, 13, 2, 12, 20, 14$ 以外，不大于 $20$ 的整数都是幸运数字。

数据规模与约定

对于全部的测试点，保证：

$1 \leq n < 10^{1201}$ ， $1 \leq m \leq 100$ ， $1 \leq \sum_{i = 1}^m |s_i| \leq 1500$ ， $\min_{i = 1}^m |s_i| \geq 1$ ，其中 $|s_i|$ 表示字符串 $s_i$ 的长度。 $n$ 没有前导 $0$ ，但是 $s_i$ 可能有前导 $0$ 。

参考代码

题解

P2536 [AHOI2005] 病毒检测

https://www.luogu.com.cn/problem/P2536

题目描述

科学家们在Samuel星球上的探险仍在继续。非常幸运的，在Samuel星球的南极附近，探险机器人发现了一个巨大的冰湖！机器人在这个冰湖中搜集到了许多RNA片段运回了实验基地。

科学家们经过几个昼夜的研究，发现这些RNA片段中有许多是未知的病毒！

每个RNA片段都是由A、C、T、G组成的序列。科学家们也总结出了Samuel星球上的“病毒模版片段”。一个模版片段是由A、C、T、G的序列加上通配符 * 和 ? 来表示。其中 * 的意思是可以匹配上0个或任意多个字符，而 ? 的意思是匹配上任意一个字母。

如果一个RNA片段能够和“病毒模版片段”相匹配，那么这个RNA片段就是未知的病毒。

例如，假设“病毒模版片段”为A*G?C。RNA片段：AGTC，AGTGTC都是未知的病毒，而RNA片段AGTGC则不是病毒。

由于，机器人搜集的这些RNA片段中除去病毒的其他部分都具有非常高的研究价值。所以科学家们希望能够分辨出其中哪些RNA片段不是病毒，并将不是病毒的RNA片段运回宇宙空间站继续进行研究。

科学家将这项任务交给了小联。现在请你为小联编写程序统计哪些RNA片段不是病毒。

输入格式

第一行有一个字符串，由A、C、T、G、*、? 组成。表示“病毒模版片段”。“病毒模版片段”的长度不超过1000。第二行有一个整数N（0<N<500），表示机器人搜集到的RNA片段的数目。随后的N行，每一行有一个字符串，由A、C、T、G组成，表示一个RNA片段。每个RNA片段的长度不超过500。注意：“病毒模版片段”和RNA片段的长度都至少为1。

输出格式

只有一行输出，为整数M，即不是病毒的RNA片段的数目。

样例 #1

样例输入 #1

A*G?C
    3
AGTC
AGTGTC
AGTGC

样例输出 #1

提示

输入中的RNA片段AGTGC不是病毒。

参考代码

题解

P2414 [NOI2011] 阿狸的打字机

https://www.luogu.com.cn/problem/P2414

题目描述

阿狸喜欢收藏各种稀奇古怪的东西，最近他淘到一台老式的打字机。打字机上只有 $28$ 个按键，分别印有 $26$ 个小写英文字母和 B、P 两个字母。经阿狸研究发现，这个打字机是这样工作的：

输入小写字母，打字机的一个凹槽中会加入这个字母(这个字母加在凹槽的最后)。
按一下印有 B 的按键，打字机凹槽中最后一个字母会消失。
按一下印有 P 的按键，打字机会在纸上打印出凹槽中现有的所有字母并换行，但凹槽中的字母不会消失。

例如，阿狸输入 aPaPBbP，纸上被打印的字符如下：

a
aa
ab

我们把纸上打印出来的字符串从 $1$ 开始顺序编号，一直到 $n$ 。打字机有一个非常有趣的功能，在打字机中暗藏一个带数字的小键盘，在小键盘上输入两个数 $(x,y)$ （其中 $1\leq x,y\leq n$ ），打字机会显示第 $x$ 个打印的字符串在第 $y$ 个打印的字符串中出现了多少次。

阿狸发现了这个功能以后很兴奋，他想写个程序完成同样的功能，你能帮助他么？

输入格式

输入的第一行包含一个字符串，按阿狸的输入顺序给出所有阿狸输入的字符。

第二行包含一个整数 $m$ ，表示询问个数。

接下来 $m$ 行描述所有由小键盘输入的询问。其中第 $i$ 行包含两个整数 $x, y$ ，表示第 $i$ 个询问为 $(x, y)$ 。

输出格式

输出 $m$ 行，其中第 $i$ 行包含一个整数，表示第 $i$ 个询问的答案。

样例 #1

样例输入 #1

aPaPBbP
3
1 2
1 3
2 3

样例输出 #1

2
1
0

提示

数据范围

对于 $100\%$ 的数据， $1\leq n\leq 10^5$ ， $1\leq m\leq10^5$ ，第一行总长度 $\leq 10^5$ 。

测试点	$n$ 的规模	$m$ 的规模	字符串长度	第一行长度
$1,2$	$1\leq n\leq 100$	$1\leq m\leq 10^3$	-	$\leq 100$
$3,4$	$1\leq n\leq 10^3$	$1\leq m\leq 10^4$	单个长度 $\leq 10^3$ ，总长度 $\leq 10^5$	$\leq 10^5$
$5\sim 7$	$1\leq n\leq 10^4$	$1\leq m\leq 10^5$	总长度 $\leq 10^5$	$\leq 10^5$
$8\sim 10$	$1\leq n\leq 10^5$	$1\leq m\leq 10^5$	-	$\leq 10^5$

参考代码

题解

P3966 [TJOI2013]单词

https://www.luogu.com.cn/problem/P3966

题目描述

小张最近在忙毕设,所以一直在读论文。一篇论文是由许多单词组成但小张发现一个单词会在论文中出现很多次，他想知道每个单词分别在论文中出现了多少次。

输入格式

第一行一个整数 $N$ ，表示有 $N$ 个单词。

接下来 $N$ 行每行一个单词,每个单词都由小写字母 $a-z$ 组成。

输出格式

输出 $N$ 个整数,第 $i$ 行的数表示第 $i$ 个单词在文章中出现了多少次。

样例 #1

样例输入 #1

3
a
aa
aaa

样例输出 #1

6
3
1

提示

数据规模与约定

$30\%$ 的数据，单词总长度不超过 $10^3$ 。
$100\%$ 的数据， $1 \leq n \leq 200$ ，单词总长度不超过 $10^6$ 。

参考代码

#include <bits/stdc++.h>
using namespace std;
int n;
int t[200020][26], tt;
int f[200020];
int s[200020];
int a[200020];
int q[200020], qq;
char c[2000020];
int ins(char *c)
{
	int p = 0;
	for (; *c; c++)
	{
		if (t[p][*c - 'a'] == 0)
		{
			t[p][*c - 'a'] = ++tt;
		}
		p = t[p][*c - 'a'];
		s[p]++;
	}
	return p;
}
int main()
{
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
	{
		scanf("%s", c);
		a[i] = ins(c);
	}
	q[qq++] = 0;
	for (int j = 0; j < qq; j++)
	{
		int u = q[j];
		for (int i = 0; i < 26; i++)
		{
			if (t[u][i])
			{
				f[t[u][i]] = u ? t[f[u]][i] : 0;
				q[qq++] = t[u][i];
			}
			else
			{
				t[u][i] = t[f[u]][i];
			}
		}
	}
	for (int i = tt; i > 0; i--)
	{
		s[f[q[i]]] += s[q[i]];
	}
	for (int i = 0; i < n; i++)
	{
		printf("%d\n", s[a[i]]);
	}
	return 0;
}

题解

P5231 [JSOI2012]玄武密码

https://www.luogu.com.cn/problem/P5231

题目背景

在美丽的玄武湖畔，鸡鸣寺边，鸡笼山前，有一块富饶而秀美的土地，人们唤作进香河。相传一日，一缕紫气从天而至，只一瞬间便消失在了进香河中。老人们说，这是玄武神灵将天书藏匿在此。

很多年后，人们终于在进香河地区发现了带有玄武密码的文字。更加神奇的是，这份带有玄武密码的文字，与玄武湖南岸台城的结构有微妙的关联。于是，漫长的破译工作开始了。

题目描述

经过分析，我们可以用东南西北四个方向来描述台城城砖的摆放，不妨用一个长度为 $n$ 的序列 $s$ 来描述，序列中的元素分别是 E，S，W，N，代表了东南西北四向，我们称之为母串。而神秘的玄武密码是由四象的图案描述而成的 $m$ 段文字。这里的四象，分别是东之青龙，西之白虎，南之朱雀，北之玄武，对东南西北四向相对应。

现在，考古工作者遇到了一个难题。对于每一段文字 $t$ ，求出其最长的前缀 $p$ ，满足 $p$ 是 $s$ 的子串。

输入格式

第一行有两个整数，分别表示母串的长度 $n$ 和文字段的个数 $m$ 。

第二行有一个长度为 $n$ 的字符串，表示母串 $s$ 。

接下来 $m$ 行，每行一个字符串，表示一段带有玄武密码的文字 $t$ 。

输出格式

对于每段文字，输出一行一个整数，表示最长的 $p$ 的长度。

样例 #1

样例输入 #1

7 3
SNNSSNS
NNSS
NNN
WSEE

样例输出 #1

4
2
0

提示

数据规模与约定

对于 $20\%$ 的数据，保证 $n \leq 100$ ， $m \leq 50$ 。
对于 $40\%$ 的数据，保证 $n \leq 2 \times 10^4$ ， $m \leq 2 \times 10^3$ 。
对于 $70\%$ 的数据，保证 $n \leq 10^6$ ， $m \leq 2 \times 10^4$ 。
对于 $100\%$ 的数据，保证 $1 \leq n \leq 10^7$ ， $1 \leq m \leq 10^5$ ， $1 \leq |t| \leq 100$ ， $s, t$ 中均只含字母 E S W N。

参考代码

题解

P3167 [CQOI2014]通配符匹配

https://www.luogu.com.cn/problem/P3167

题目描述

几乎所有操作系统的命令行界面(CLI)中都支持文件名的通配符匹配以方便用户。最常见的通配符有两个，一个是星号(”“')，可以匹配0个及以上的任意字符：另一个是问号(”？“)，可以匹配恰好一个任意字符。现在需要你编写一个程序，对于给定的文件名列表和一个包含通配符的字符串，判断哪些文件可以被匹配。

输入格式

第一行是一个由小写字母和上述通配符组成的字符串。第二行包含一个整数n，表示文件个数。接下来n行，每行为一个仅包含小写字母字符串，表示文件名列表。

输出格式

输出n行，每行为”YES“或”NO“，表示对应文件能否被通配符匹配。

样例 #1

样例输入 #1

*aca?ctc
6
acaacatctc
acatctc
aacacatctc
aggggcaacacctc
aggggcaacatctc
aggggcaacctct

样例输出 #1

YES
YES
YES
YES
YES
NO

提示

对于1 00%的数据

·字符串长度不超过1 00000

· 1 <=n<=100

·通配符个数不超过10

参考代码

题解

P2336 [SCOI2012]喵星球上的点名

https://www.luogu.com.cn/problem/P2336

题目描述

a180285 幸运地被选做了地球到喵星球的留学生。他发现喵星人在上课前的点名现象非常有趣。

假设课堂上有 $n$ 个喵星人，每个喵星人的名字由姓和名构成。喵星球上的老师会选择 $m$ 个串来点名，每次读出一个串的时候，如果这个串是一个喵星人的姓或名的子串，那么这个喵星人就必须答到。

然而，由于喵星人的字码如此古怪，以至于不能用 ASCII 码来表示。为了方便描述，a180285 决定用数串来表示喵星人的名字。

现在你能帮助 a180285 统计每次点名的时候有多少喵星人答到，以及 $m$ 次点名结束后每个喵星人答到多少次吗？

输入格式

首先定义喵星球上的字符串给定方法：

先给出一个正整数 $l$ ，表示字符串的长度，接下来 $l$ 个整数，第 $i$ 个整数 $a_i$ 表示字符串的第 $i$ 个字符。

输入的第一行有两个整数，分别表示喵星人的个数 $n$ 个点名次数 $m$ 。
接下来 $n$ 行，每行两个喵星球上的字符串，按照定义的方法给出，依次表示第 $i$ 只喵的姓和名。
接下来 $m$ 行，每行一个喵星球上的字符串，表示一个老师点名的串。

输出格式

对于每个老师点名的串，输出一行一个整数表示有多少只喵答到。
然后在最后一行输出 $n$ 个用空格隔开的整数，第 $i$ 个整数表示第 $i$ 个喵星人被点到的次数。

样例 #1

样例输入 #1

2 3
6 8 25 0 24 14 8 6 18 0 10 20 24 0
7 14 17 8 7 0 17 0 5 8 25 0 24 0
4 8 25 0 24
4 7 0 17 0
4 17 0 8 25

样例输出 #1

提示

样例 1 解释

事实上样例给出的数据如果翻译成地球上的语言可以这样来看

2 3
izayoi sakuya
orihara izaya
izay
hara
raiz

数据规模与约定

对于 $30\%$ 的数据，保证 $n, m \le 10^3$ ，喵星人的名字总长不超过 $4\times10^3$ ，点名串的总长不超过 $2\times10^3$ 。
对于 $100\%$ 的数据，保证 $1 \leq n\le 5 \times 10^4$ ， $1 \leq m \le 10^5$ ，喵星人的名字总长和点名串的总长分别不超过 $10^5$ ，保证喵星人的字符串中作为字符存在的数不超过 $10^4$ 。

参考代码

题解

P2603 [ZJOI2008]无序运动

https://www.luogu.com.cn/problem/P2603

题目描述

D博士对物理有着深入的研究，经典物理、天体物理、量子物理都有着以他的名字命名的定理。最近D博士着迷于研究粒子运动的无规则性。对圣经深信不疑的他相信，上帝创造的任何事物必然是有序的、有理可循的，而不是无规则的、混沌的。

经过长时间的研究，D博士找到了很多出现相当频繁的轨迹片断，他把这些轨迹片断储存在一个很大的数据库内。他需要你帮助他写一个程序，对于一个给出的粒子运动轨迹，统计数据库中每个轨迹片断的出现的次数。

为清楚起见，我们定义一个粒子的轨迹为二维平面上的一个点列（P1, P2, … PN）。点列P的一个子列[i, j]定义为P中一段连续的子序列（Pi, Pi+1, … Pj）。点列P的一个子列[u, v]被称为点列Q = (Q1, Q2 … Qv-u+1)在P中的一次出现，当且仅当Q经过有限次的平移、旋转、翻转、放缩之后得到Q’满足Q’k = Pu+k-1（k = 1 … u – v + 1）。

输入格式

输入文件movement.in第一行两个整数N、M，分别描述待处理的粒子运动轨迹的点列大小与数据库内的轨迹片断个数。

接下来M行依次给出每个轨迹片断。每行先是一个正整数K，表示该轨迹片断点列的长度。然后2K个整数，依次描述点列中的K个点的横坐标与纵坐标。

接下来一行2N个整数，依次描述待处理的粒子运动轨迹的点列中N个点的横坐标与纵坐标。

注：输入中的每条轨迹中任意相邻两点不会相同。

输出格式

输出文件movement.out应包含M行，依次给出每个片段在待处理运动轨迹中的出现次数。

样例 #1

样例输入 #1

3 2
2 17 0 10 1
3 0 0 1 0 1 -1
0 0 1 0 1 1

样例输出 #1

2
1

提示

对于30%的测试数据，N, M, K ≤ 100，片段总长度 ≤ 500;

对于50%的测试数据，N, M, K ≤ 1 000，片段总长度 ≤ 5 000;

对于100%的测试数据，满足N, K ≤ 200 000，片段总长度 ≤ 200 000，输入中给出所有点坐标绝对值均不大于10 000。

参考代码

题解

P3715 [BJOI2017]魔法咒语

https://www.luogu.com.cn/problem/P3715

题目描述

Chandra 是一个魔法天才。

从一岁时接受火之教会洗礼之后，Chandra 就显示出对火元素无与伦比的亲和力，轻而易举地学会种种晦涩难解的法术。这也多亏 Chandra 有着常人难以企及的语言天赋，让她能轻松流利地说出咒语中那些极其拗口的魔法词汇。

直到十四岁，开始学习威力强大的禁咒法术时，Chandra 才遇到了障碍。

根据火之魔法规则，禁咒的构成单位是 N 个基本词汇。施法时只要凝聚精神力，说出一段用这些词语组成的长度恰好等于 L 的语言，就能释放威力超乎想象的火法术。过去的魔法师们总结了几种表达起来最连贯的组合方式，方便施法者以最快语速完成法术。

但具有魔法和语言双重天才的 Chandra 不满足于这几种流传下来的禁咒，因为她可以毫无困难地说出普通人几乎不可能表达的禁咒语句。然而，在实际施法时，Chandra 发现有些自创禁咒念出后不但没有预期效果，反而会使自己的精神力迅速枯竭，十分难受。

这个问题令 Chandra 万分不解。她大量阅读典籍，到处走访魔法学者，并且不顾精神折磨一次又一次尝试新咒语，希望找出问题的答案。

很多年过去了，在一次远古遗迹探险中，Chandra 意外闯进了火之神艾利克斯的不知名神殿。根据岩土特征分析，神殿应该有上万年的历史，这是极其罕见的。Chandra 小心

翼翼地四处探索，沿着魔力流动来到一间密室。她看见密室中央悬浮着一本书籍。在魔法保护下书籍状况完好。精通上古语言的 Chandra 读过此书，终于解开了多年的困惑。

禁咒法术之所以威力强大，是因为咒语借用了火之神艾利克斯的神力。这本书里记载了艾利克斯生平忌讳的 M 个词语，比如情敌的名字、讨厌的植物等等。使用禁咒法术时，如果语言中含有任何忌讳词语，就会触怒神力而失效，施法者也一并遭受惩罚。

例如，若 ”banana” 是唯一的忌讳词语，“an”、”ban”、”analysis” 是基本词汇，禁咒长度须是 11，则“bananalysis” 是无效法术，”analysisban”、”anbanbanban”是两个有效法术。注意：一个基本词汇在禁咒法术中可以出现零次、一次或多次；只要组成方式不同就认为是不同的禁咒法术，即使书写形式相同。

谜题破解，Chandra 心情大好。她决定计算一共有多少种有效的禁咒法术。

由于答案可能很大，你只需要输出答案模 1,000,000,007 的结果。

输入格式

第一行，三个正整数 N, M, L。

接下来 N 行，每行一个只含小写英文字母的字符串，表示一个基本词汇。

接下来 M 行，每行一个只含小写英文字母的字符串，表示一个忌讳词语。

输出格式

仅一行，一个整数，表示答案（模 10^9+7）。

样例 #1

样例输入 #1

4 2 10
boom
oo
ooh
bang
ob
mo

样例输出 #1

样例 #2

样例输入 #2

3 1 3
a
ab
aba
aaa

样例输出 #2

样例 #3

样例输入 #3

3 1 14
ban
an
analysis
banana

样例输出 #3

提示

【样例解释 1】

有效的禁咒法术共有 14 种：boom/bang/oo，oo/oo/oo/oo/oo，oo/oo/ooh/ooh，

oo/ooh/oo/ooh，oo/ooh/ooh/oo，ooh/oo/oo/ooh，ooh/oo/ooh/oo，

ooh/ooh/boom，ooh/ooh/oo/oo，ooh/ooh/bang，ooh/bang/ooh，

bang/oo/oo/oo，bang/ooh/ooh，bang/bang/oo。

【样例解释 2】

有效的禁咒法术有 a/ab, ab/a, aba 共三种。注意，ab/a 和 aba 算

成两种不同的禁咒法术。

【数据规模与约定】

本题一共有 10 个测试点。

下表是每个测试点的数据规模和约定：

对于 100%的数据，1 ≤ N, M ≤ 50，1 ≤ L ≤ 10^8，基本词汇的长度之和不超过100，忌讳词语的长度之和不超过 100。保证基本词汇不重复，忌讳词语不重复。

参考代码

题解

P2292 [HNOI2004] L 语言

https://www.luogu.com.cn/problem/P2292

题目描述

标点符号的出现晚于文字的出现，所以以前的语言都是没有标点的。现在你要处理的就是一段没有标点的文章。

一段文章 $T$ 是由若干小写字母构成。一个单词 $W$ 也是由若干小写字母构成。一个字典 $D$ 是若干个单词的集合。我们称一段文章 $T$ 在某个字典 $D$ 下是可以被理解的，是指如果文章 $T$ 可以被分成若干部分，且每一个部分都是字典 $D$ 中的单词。

例如字典 $D$ 中包括单词 $\texttt{is},\texttt{name},\texttt{what},\texttt{your}$ ，则文章 $\texttt{whatisyourname}$ 是在字典 $D$ 下可以被理解的，因为它可以分成 $4$ 个单词： $\texttt{what},\texttt{is},\texttt{your},\texttt{name}$ ，且每个单词都属于字典 $D$ ，而文章 $\texttt{whatisyouname}$ 在字典 $D$ 下不能被理解，但可以在字典 $D'=D\cup\{\texttt{you}\}$ 下被理解。这段文章的一个前缀 $\texttt{whatis}$ ，也可以在字典 $D$ 下被理解，而且是在字典 $D$ 下能够被理解的最长的前缀。

给定一个字典 $D$ ，你的程序需要判断若干段文章在字典 $D$ 下是否能够被理解。并给出其在字典 $D$ 下能够被理解的最长前缀的位置。

输入格式

第一行两个整数 $n$ 和 $m$ ，表示字典 $D$ 中有 $n$ 个单词，且有 $m$ 段文章需要被处理。

接下来 $n$ 行，每行一个字符串 $s$ ，表示字典 $D$ 中的一个单词。

接下来 $m$ 行，每行一个字符串 $t$ ，表示一篇文章。

输出格式

对于输入的每一篇文章，你需要输出一行一个整数，表示这段文章在字典 $D$ 可以被理解的最长前缀的位置。

样例 #1

样例输入 #1

4 3 
is
name
what
your
whatisyourname
whatisyouname
whaisyourname

样例输出 #1

14
6
0

提示

样例 1 解释

对于第一个询问，整段文章 whatisyourname 都能被理解。
对于第二个询问，前缀 whatis 能够被理解。
对于第三个询问，没有任何前缀能够被理解。

数据规模与约定

对于 $80\%$ 的数据，保证 $m \leq 20$ ， $|t| \leq 10^6$ 。
对于 $100\%$ 的数据，保证 $1 \leq n \leq 20$ ， $1 \leq m \leq 50$ ， $1 \leq |s| \leq 20$ ， $1 \leq |t| \leq 2 \times 10^6$ ， $s$ 与 $t$ 中均只含小写英文字母。

提示

请注意数据读入对程序效率造成的影响。
请注意【数据规模与约定】中标注的串长是单串长度，并不是字符串长度和。

说明

本题数据有加强，其中前 $80\%$ 的数据为原测试数据。

参考代码

题解

P4600 [HEOI2012]旅行问题

https://www.luogu.com.cn/problem/P4600

题目描述

yz 是 Z 国的领导人，他规定每个地区的名字只能为 26 个小写拉丁字母的一个。由于地区数有可能超过 26 个，便产生了一个问题，如何辨别名字相同的地区？于是 yz 规定，一个地区的描述必须包含它的所有上级，且上级按次序排列。于是，一个地区的描述是一个字符串。比如说，一个地区的名字为 $c$ ，它的上级为 $b$ ， $b$ 的上级为 $a$ ， $a$ 没有上级，那么这个地区就描述为 $abc$ 。显然，这个描述同时包含了 $c$ 的上级 $b$ 和 $b$ 的上级 $a$ 的描述，分别为 $ab$ 和 $a$ 。

值得注意的是，每个地区最多有一个上级，同一上级的地区之间名字不同，没有上级的地区之间名字不同。

现在，yz 对外公布了 $n$ 个地区的描述，这些描述中包含了 Z 国所有地区的描述，并让你处理来访者的旅行问题。

现有 $m$ 对人访问这个国家，对于每对人，第一个人喜欢第 $i$ 个描述中的第 $j$ 个地区，设这个地区描述为 $s1$ ，第二个人喜欢第 $k$ 个描述中的第 $l$ 个地区，设这个地区描述为 $s2$ 。他们为了统一行程，决定访问描述为 $s$ 的地区（显然他们只关心地区的名字，并非是地区本身），设 $s$ 的长度为 $t$ ， $s$ 需要满足以下条件：

1： $t\leq j$ , $t\leq l$ ;

1： $s[1\cdots t] = s1[j-t+1\cdots j]$ , $s[1\cdots t] = s2[l-t+1\cdots l]$ ；（（即 $s$ 为 $s1$ 中 $1$ 到 $j$ 位与 $s2$ 中 $1$ 到 $l$ 位的公共后缀））

2： $t$ 最大化。为了不使输出过大，你只需把这个字符串按照如下生成的 $26$ 进制数转成 $10$ 进制后 $mod 1000000007$ 后输出:

a->0

b->1

z->25

比如地区 cab 被编码成 $2\times26^2 + 0\times26^1 + 1\times26^0 = 1353$ 。

输入格式

第一行给定一个整数 $n$

第 $2\cdots n+1$ 行:每 $i+1$ 行给定一个字符串 $a[i]$ ,表示第 $i$ 个描述。

接下来一行一个整数 $m$

接下来 $m$ 行:每行给定四个整数 $i,j,k,l$ ，字母含义与题目描述一致。

输出格式

共 $m$ 行，每行一个整数，表示答案字符串的编码。

样例 #1

样例输入 #1

2
aabb
babb
2
1 3 2 3
1 4 2 4

样例输出 #1

1
1

提示

【样例说明】

询问 1 中的公共后有 ab 和 b，但是没有 ab 这个地区，只有 b 地区，所以只能选择 b 这个地区；

询问 2 中的公共后有 abb、bb 和 b，但是没有 abb 和 bb 这两个地区，只有 b 地区，所以只能选择 b 这个地区。

【数据范围】

设这个国家地区总数数为 tot（注意：输入的字符串总长度可能超过 tot！）

对于 30%的数据，满足 tot，m，n<=100；

对于 50%的数据，满足 tot，m，n<=1000；

对于 80%的数据，满足 tot，m，n<=100000；

对于 100%的数据，满足 tot，m，n<=1000000；

保证输入文件不超过 20MB。

HEOI 2012 Day2 Task2

参考代码

题解

https://www.luogu.com.cn/problem/P4600
输入n个字符串
m个询问
每次询问两个字符串的前缀
第i个串的前j个字符
第k个串的前l个字符
找到最长的一个子串
是第i个串的前j个字符的后缀
是第k个串的前l个字符的后缀
是所有串中某一个的前缀
输出这个串的 hash 值（26进制，mod 1000000007）

hash(aba) = hash(ab) * 26 + a
Trie树上每一个点的hash值是自己父亲节点*26 + 边的字符

aba_abab_bab_
0123456789

st[0] = 0
st[1] = 4
st[2] = 9

'\0'

abaababbab
0123456789

st[0] = 0
st[1] = 3
st[2] = 7

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<queue>
using namespace std;
int f[1000020][26],ff=1;
int g[1000020];
int d[1000020];
int h[21000020];
int v[1000020];
char s[21000020],*ss=s;
char *st[1000020];
int n,m,xa,xb,ya,yb;
void ins(char s[])
{
	int p=1;
	for(int i = 0;s[i];i++)
	{
		if(!f[p][s[i]-'a'])
			f[p][s[i]-'a']=++ff;
		p=f[p][s[i]-'a'];
		h[ss - s + i]=p;
	}
}
int lca(int x,int y)
{
	if(d[x]<d[y])
		swap(x,y);
	for(int i=19;i>=0;i--)
		if(d[y]<=d[f[x][i]])
			x=f[x][i];
	if(x==y)
		return x;
	for(int i=19;i>=0;i--)
		if(f[x][i]!=f[y][i])
			x=f[x][i],y=f[y][i];
	return f[x][0];
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%s",ss);
		st[i]=ss;
		ins(ss);
		ss+=strlen(ss);
	}
	queue<int>q;
	q.push(1);
	d[1]=1;
	while(q.size())
	{
		int u=q.front(),x,j;
		q.pop();
		for(int i=0;i<26;i++)
			if(x=f[u][i])
			{
				for(j=g[u];j;j=g[j])
					if(f[j][i])
						break;
				g[x]=j?f[j][i]:1;
				if(!d[g[x]])
					while(1);
				d[x]=d[g[x]]+1;
				v[x]=(v[u]*26LL+i)%1000000007;
				q.push(x);
			}
	}
	memset(f,0,sizeof f);
	for(int i=1;i<=ff;i++)
		f[i][0]=g[i];
	for(int j=1;j<20;j++)
		for(int i=1;i<=ff;i++)
			f[i][j]=f[f[i][j-1]][j-1];
	scanf("%d",&m);
	for(int i=0;i<m;i++)
	{
		scanf("%d %d %d %d",&xa,&xb,&ya,&yb);
		printf("%d\n",v[lca(h[&st[xa][xb-1]-s],h[&st[ya][yb-1]-s])]);
	}
	return 0;
}