字符串题目选做

基本概念

后缀数组的构建。

height和lcp的应用：表示排名相邻的两个后缀的lcp。

总的lcp：st表区间min。

后缀自动机的构建。

挖掘parent树的性质，关注集合中endpos相等的条件。

一.后缀数组部分

1.1 [AHOI2013]差异

$\sum_{1\le i< j\le n}len(suf_i)+len(suf_j)-2\times lcp(suf_i,suf_j)\\=\sum_{1\le i< j\le n}len(suf_i)+len(suf_j)-2\sum_{1\le i< j\le n}\times lcp(suf_i,suf_j)\\=\frac {n(n+1)}{2}(n-1)-2\sum_{1\le i< j\le n}\times lcp(suf_i,suf_j)$

求所有后缀的lcp。

考虑每个height的贡献：找到它能作为区间最小值的区间。

也就是找height的前缀最小值，它的位置记为pos。

那么 $[pos,i]$ 的区间都有它贡献了。

把贡献记为 $f$ 数组，那么可以继承pos的f贡献。

类似dp的方式统计。

1.2 [SDOI2016]生成魔咒

题意：求字符串S的任意前缀的不同非空字串数。

看到前缀，自然想到反转后来求后缀。

容易发现，后面的后缀完全包含原来的，所以只要求新贡献就行了。

考虑容斥，和其他后缀的不同的长度：$len_i-height_i$。

由于我们是按照后缀来考虑串，而height是比较排名。

我们难免会比较到在他之前被考虑过的字符串。

可以用链表倒序删除来规避这种情况。

1.3 [BJWC2010]外星联络

提供一种看起来是$O(n^2)$ 但是比较快的做法。

因为不用关注子串，只看长度。

可以发现height数组中的每一个值，都对应了一种出现次数大于1的子串。

那么我们就可以通过枚举height值来求解子串长度。

对于一个确定的子串要找到他所有的出现次数。

也就是从这个height开始，找到所有长度>=当前长度的height排名最远是多少，记为k。

那么总共的出现次数：k-i+1。i为当前排名。

由于是lcp，所以已经再两个串中出现了，所以k-i要加1。

为了防止算重，要从上一个height+1的位置开始枚举。

1.4 [SDOI2008]Sandy的卡片

首先要将字符串差分，满足同时加减的条件。

为了方便考虑这n个串的子串，我们把它们首位相接拼成一个大串。

中间用不相关的字符加起来。

我们要求这个串的n个后缀的lcp最大是多少。

具有单调性，可以二分解决。

还需要满足这n个后缀所属的串互不相同，可以用pos维护每个位置所属的串。

只要这些串都能在当前长度下找到lcp，就是合法情况。

由于求的是差分数组，所以对应回原数组还要把答案加1。

相当于：|——|——|——|——| 原数组

​ | | | | 差分数组

2.后缀自动机部分

2.1 SP705 SUBST1 - New Distinct Substrings

parent树上，儿子和父亲相差的 $|len|$ 就是新增加的字符。

这样保证了每个字符只被统计一次。

所以是本质不同的。

2.2.1 SP1811 LCS - Longest Common Substring

这里有一个比较常见的模型：统计LCS。

建好SAM后，我们把第二个串放在上面跑。

对于 $s_i$ 匹配的节点，当前的Common Substring就是 $s_i$ 代表的最长串。

我们考虑 $s_{i+1}$ 的转移。

• 如果 $s_i$ 能产生 $s_{i+1}$ 的出边，那么说明该串能够识别这个子串，直接让ans++即可

• 如果不行，那么我们就在parent树上向上跳。

  因为当前节点的父亲是它的后缀，所以也可能匹配。

  这时 $ans=len_{fa}+1$ 。

• 如果跳到 $0$ 了还不行，那么将 $ans=0$ 重新开始。

对所有情况取 $\max$ 即可。

inline void get_ans()
{
	int p=1,le=0,mx=strlen(s2+1);
	for(int i=1;i<=mx;i++)
	{
		int c=s2[i]-'a'+1;
		if(tri[p][c]) p=tri[p][c],++le;
		else 
		{
			while(!tri[p][c]&&p) p=fa[p];
			if(!p) le=0,p=1;
			else le=len[p]+1,p=tri[p][c];
		}
		ans=max(ans,le);
	}
}

2.2.2 SP1812 LCS2 - Longest Common Substring II

和上题类似，这次是多串LCS。

还是可以对第一个串建SAM，把剩下的串向上跑。

关键是我们怎么通过两两串的LCS推知总共的LCS。

可以在匹配串的时候，将已经匹配的长度 $len$ 记录在点上。

表示这个节点最多能匹配的长度。

当有多个串匹配到当前节点时，我们要把他们的 $mx$ 取 $\min$ 作为答案。

因为肯定是最短的那一个作为CS。

我们把每个节点的 $mn$ 取 $\max$ 即为LCS。

注意在更新时要考虑它的father，因为在不超过长度的限制下，他所能匹配的长度一定father也能匹配（后缀关系），但可能未被更新。

用基数排序求拓扑序实现。

2.3 [HAOI2016]找相同字符

还算小清新题。

对于两个串的子串，统计它们在A，B两串中的出现次数。

通过上文知道，本质不同的子串可以通过len来计算。

建好A的后缀自动机后，我们可以统计B在上面匹配的长度 $le$。

考虑和每个节点的匹配长度 $le'$，我们知道后缀在同一个endpos等价类里面是连续的。

所以每一个新增加的本质不同的子串都能和当前等价类的任意一个后缀进行匹配（子串）。

又因为新增加的子串长度为 $le'-(mnlen-1)=le'-mxlen_{fa}$ 。

再乘上集合大小siz即可。（拓扑序求）

注意：如果每个节点每次都要遍历一边，复杂度为 $O(|S|^2)$，无法接受。

所以可以提前预处理出匹配了最大长度len的贡献，做一遍前缀和。这样只用考虑最后的节点了。

3.AC自动机部分

3.1 [HAOI2017]字符串

考虑转化题意：要求的条件即 $\mathrm{|s|\le lcp+lcs+k}$ 。

那么我们可以通过枚举lcp的长度，从而确定合法的方案。

对文本串的正串反串都建立AC自动机，那么此时便能识别它的前缀和后缀。

此时我们再把模式串放上去，将它访问过的节点都加一。

那么不难发现，只有这些位置是有贡献的。

也就是只有文本串的对应后缀(pos+k+1)覆盖了这些位置，才能计入当前文本串的答案。

所以建立fail树，所求的初步答案即后缀节点子树和。

可以通过树状数组维护dfs序实现，即dfs前后两次做差。

但我们发现，在 $\mathrm{|s|< lcp+lcs+k}$ 时，对于 $|s| $ 的每个位置，我们都统计了一遍。

也就是说 $||s|-\mathrm{lcp+lcs+k}|$ 这些长度被多算了。

而 $pos+k$ 的位置对应的子树和恰好对应它们，所以再挂上相关的询问即可。