Day 6——字符串

一、哈希（哈希）

把信息量大的东西压缩成信息量小的表达。

例题一、

给出两个排列$a,b$，长度分别为$n,m$，你需要计算有多少个$x$，使得$a_1+x,a_2+x,a_3+x,…,a_n+x$是$b$的子序列。
$n\le m\le2\times 10^5$

思路

枚举$b$中与$a$匹配的最大值$x$，把$x-n+1$

例题二、

你可以通过交换字母来修改字符串。
如果两个字符串经过这样的变换之后可以相等，则称它们相似。
给出一个文本串$T$与一个模式串$P$，询问$T$中有哪些子串与$P$一模一样或相似。
$|T|,|P|\le10^6$

思路

考虑如何判断两个字符串相似。
记录$last_i$表示上一次出现$p_i$的位置，我们发现两个字符串的$last$数组相同，他们就是相似的。
然后直接KMP比较（或者哈希）。

二、KMP

求出$next$数组，$next_i$表示当第$i$个位置失配的时候，应该从后面的什么位置开始匹配。
求最长公共前后缀，这样就可以求出$next$数组。

模板

char s[N], t[N];
int nt[N];
inl void getnext()
{//模式串与自己匹配求出next数组
	rg int len = strlen(t), i = 0, j = -1;
	while (i < len)
	{
		if (j == -1 || t[i] == t[j])nt[++i] = ++j;
		else j = nt[j];
	}
}
inl void kmp()
{
	getnext();
	rg int lens = strlen(s),lent=strlen(t), i = 0, j = 0;
	while (i < lens)
	{
		if (j == -1 || s[i] == t[j])
		{
			++i, ++j;
			if (j == lent)
			{
				j = nt[j];
				//此时[i-lent+1,i-1]的子串是与t串匹配的
			}
		}
		else j = nt[j];
	}
}

例题一、

给出一个长度为$n$的串$S$，判断$S$的每个前缀是不是循环串，如果是输出最大循环次数。
循环串的定义：由一个相同的串重复至少两次拼成。
$n\le10^6$

思路

如果一个串是循环串，那么这个串就是$m$个小串的拼接，他的$next$就是$m-1$个小串。
由于$s_{1…next}$与$S_{n-next…next}$是相同的两串，那么只要$i\mod(i-next)=0$，那么该串是一个以$i-next$为最小循环节的串。

例题二、

给出一个长度为$n$的串$S$，你需要选取$S$的一个前缀$T$，使得$T$重复若干次可以拼出$S$（拼合可以有部分重复，但是重复部分必须相同）。
最小化$T$的长度
$n\le10^6$

思路

根据$next$建出$fail$树，贪心即可。

三、AC自动机（Aho-Corasick automation）

例题一、

给出含有$n$个单词的词典，你需要计算对于所有长度为$m$的字符串，有多少个至少包含一个单词。
字符集为大写字母。
$n\le60,m\le100,$每个单词长度$\le100$

思路

建出AC自动机，将每个单词结尾设为不可通行，计算从根节点开始走$m$步的总方案数，用总字符串数$-$总方案数即可。

例题二、

给出$n$个字符串和$m$个询问，每次询问$i,j,k,l$，求第$i$个串的$j$长前缀和第$k$个串的$l$长前缀的最长公共后缀。
$\sum S_i\le10^6$

思路

建出AC自动机，求所求两个前缀在$fail$树上的LCA即可。

例题、三

给定$n$个字符串$s_i$，问最多能从中选择多少个串，使得其中不存在一个串是另一个串的子串。
$n\le750,\sum|s_i|\le10^7,s_i\in\left\{a,b\right\}$

思路

四、后缀数组（SA）

模板

int rk[N], sa[N], b[N], m, n, tong[N], height[N];
char s[N];
inl void radix_sort()
{
	memset(tong, 0, sizeof(tong));
	for (rg int i = 1; i <= n; ++i)++tong[rk[b[i]]];
	for (rg int i = 1; i <= m; +i)tong[i] += tong[i - 1];
	for (rg int i = n; i >= 1; --i)sa[tong[rk[b[i]]]--] = b[i];
}
inl void getsa()
{
	for (rg int i = 1; i <= n; ++i)rk[i] = s[i] - 'a' + 1, b[i] = i;
	radix_sort();
	for (rg int k = 1; k <= n; k <<= 1)
	{
		rg int tot = 0;
		for (rg int i = n - k + 1; i <= n; ++i)b[+tot] = i;
		for (rg int i = 1; i <= n; ++i)if (sa[i] > k)b[++tot] = sa[i] - k;
		radix_sort(); memcpy(b, rk, sizeof(b)); rk[sa[tot = 1]] = 1;
		for (rg int i = 2; i <= n; ++i)
			if (b[sa[i]] == b[sa[i - 1]] && b[sa[i] + k] == b[sa[i - 1] + k])rk[sa[i]] = tot;
			else rk[sa[i]] = ++tot;
		if (tot == n)break;
		m = tot;
	}
}
inl void getheight()
{
	rg int k = 0;
	for (rg int i = 1; i <= n; ++i)rk[sa[i]] = i;
	for (rg int i = 1; i <= n; ++i)
	{
		if (rk[i] == 1)continue;
		rg int j = sa[rk[i] - 1];
		while (j + k <= n && i + k <= n && s[j + k] == s[i + k])++k;
		height[rk[i]] = k;
	}
}

例题一、

给出$n$个串，找出一个最长的子串，至少在$\dfrac{n}{2}$个串中出现过。
$\sum S_i\le10^5$

思路

将所有字符串拼起来，求$SA$和$Height$，做滑动窗口，求RMQ。

结论

一个字符串的不同子串个数为$\dfrac{n(n-1)}{2}\sum\limits_{i=1}^{n}Height_i$

例题二、

给出一个小写字符串$S$以及$m$个询问，每个询问给出两个正整数$x,y$（$x\le y\le$字符串$S$本质不同的子串个数），表示询问$s$的所有本质不同的子串中，字典序排名为$x$到$y$之间的所有字符串的哈希值总和（包括$x$和$y$）。
$|S|,m\le10^5$

思路

考虑转化为对前缀的查询，避免对两个子串的相同前缀重复计算，我们只用对不相同的部分二分求

例题三、

给出一个字符串，将其划分为不超过$k$个连续子串。设第$i$个子串为$s_i$，对于每个$s_i$，找到其中字典序最大的连续子串$c_i$。
你需要找到一种划分，使得字典序最大的$c_i$字典序最小。
$|S|\le10^6$

思路

二分字典序，每次从后往前考虑，使得每个子串字典序不超过二分的答案，统计字典序的方法：二分一个后缀，再在后缀上二分。

例题四、

给定一个字符串$S$，有$m$个询问，每组询问形如$(a,b,c,d)$，询问$S_{a…b}$的所有子串中与$S_{c…d}$的最长公共前缀的最大值是多少。
$|S|\le10^5m\le10^5$

思路

二分答案$x$，找到$SA$中与后缀$c$LCP大于$x$的部分，查询是否含有$[a,b]$中的元素，二维数点问题，主席树求解。

例题五、

给出一个长度为$n$的数组$a_i=i$，把它进行$m$次操作，每次操作可以是以下两种：

把某一段提到开头
区间翻转

现在问后缀数组为$a$的字符串$S$有多少种可能。限制$S$为字符串中出现的都是正整数，且最大元素等于不同元素的个数。
$n\le10^9,m\le10^5$

思路

考虑后缀数组的定义$suf_{a_i}<suf_{a_{i+1}}$
于是推出$S_{a_i}\le S_{a_{i+1}}$
可以发现确定每一个$\le$为$<$或$=$，就能唯一确定整个数组。
取$<$一定合法，
取$=$要求$suf_{a_{i+1}}<suf_{a_{i+1}+1}$

五、后缀自动机（SAM）

字符串$S$的后缀自动机是一个能接受$S$的所有子串的有限状态自动机。

Right集

所有该字符串的右端点组成的集合称为该串的$Right$集，$Right$集不同的串即为本质不同的串
子串的$Right$集只有包含与并列关系
由于这样的性质，我们可以建出一棵树，这棵树称为$fail$树。

建立SAM

$last$:已经建立好的$SAM$因为新后缀而创建的最后一个节点。