字符串总结

Hash

Hash 是最简单同时也是泛用性最强的字符串算法。它的思想很简单：设计 Hash 函数 $f$，两个字符串的 hash 函数值一样时两个字符串一样，否则两个字符串不一样。在设计 Hash 函数时，我们主要关心的是时间复杂度和准确率。例如有一些提高准确率的方法：自然溢出、多模数 Hash……

在大多数情况下，形如 $f(x)=A+Bx+Cx^2\cdots$ 是一种简单高效的 Hash。下面的 Skip 也是基于这种 Hash 方法。

Skip：快速得到子串 Hash 值

给定一个串 $s$，每次查询子串 $s[l:r]$ 的 Hash 值。

设 $g(i)$ 表示 $s[1:i]$ 的 Hash 值。

考虑我们的 $hash$ 函数时实际上是一个多项式，那么有 $g(i)=x*g(i-1)+b$。

可以发现，对于前 $l-1$ 个元素，它们对 $g(r)$ 的贡献为 $x^{r-l+1}g(l-1)$。

将这个贡献减掉，就可以得到正确的 $Hash$ 值。

即 $f(s[l:r])=f([s[1:r]])-x^{r-l+1}f(s[1:l-1])$。

KMP 求前缀函数

给定一个长度为 $n$ 的字符串 $s$，其 前缀函数 被定义为一个长度为 $n$ 的数组 $\pi$ 。其中 $\pi[i]$ 的定义是：

$s[1:i]$ 的最长真 border 长度。

这里不妨先讲一下 border。

border 和 border 的性质

Hillary: Open the border.

Trump: Build a wall.

DAN: I AK IOI.

border 是一个字符串相同前缀和后缀。

例如在字符串 daniel_dandandan 中，$\varnothing,dan,daniel$_$dandandan$ 都是该字符串的 border。

• border 的性质

字符串 $S$ 的所有 border 可以被划分成不超过 $\log_2|S|$ 段，每一段的长度是等差数列。

证明：

• 引理 $1$：若字符串 $S$ 存在一个长度为 $k$ 的 border，那么 $|S|-k$ 为字符串的一个周期。

• 引理 $2$：若 $p,q$ 为字符串的周期且 $p+q\le|S|-gcd(p,q) $，那么 $gcd(p,q)$ 也为字符串的一个周期。

考虑 border 大于 $\frac{|S|}{2} $ 的情况，由引理一得 $q=|S|-k $ 为 $S$ 的最小周期，其中 $k$ 为 $S$ 的最长 border，由引理二得 $|S|-aq\geq \frac{|S|}{2} $ 为 $S$ 的 $border$。

递归证明 border 小于 $\frac{|S|}{2} $ 即可。

回文 border 是一个回文的 border。

类似地，回文 border 也有如上性质，读者可以自行证明。

这里只给出结论：字符串 $S$ 的所有回文 border 可以被划分成不超过 $\log_2|S|$ 段，每一段的长度是等差数列。

这里继续讲前缀函数和 KMP。

KMP 是一个高效的求前缀函数的算法。

这个算法其实很简单。假设我们已经求出了前 $i$ 个位置的前缀函数。求第 $i+1$ 个位置的时候我们不停地跳前缀匹配就行了。

1
2

while(k&&s2[k+1]!=s2[i+1])k=nxt[k];
nxt[i+1]=(s2[i+1]==s2[k+1])?(++k):0;

代码就两行。

因为 while 每执行一次 $k$ 至少减少 $1$，$k$ 最多增加 $n$ 所以复杂度是线性的。

Manacher

Manacher 算法可以求出以每个位置为回文中轴的回文半径。

用前面提到的 $ Hash$ 算法套二分可以在 $O(n\log_2n)$ 的时间复杂度求解。而 Manacher 算法可以做到 $O(n)$。

我们始终维护一个最靠右的最长回文串 $s[l:r]$，记它的中轴为 $mid$。对于以 $x$ 为回文中心的回文串，可以直接找到与它关于$mid$ 对称的位置的回文半径，此时要保证回文串不超过 $r$，因为 $r$ 的右边是未知的，所以要和 $r-x+1$ 取 min，并从回文半径开始更新。最后再更新 $s[l:r]$。

代码：

1
2
3

if(t<=r)ans[t]=min(ans[2*mid-t],r-t+1);
while(b[ans[t]+t]==b[t-ans[t]])ans[t]++;
if(t+ans[t]>r)r=t+ans[t]-1,mid=t;

复杂度分析:

当第一行执行完 t+ans[t]-1<r 时。第二行 ans[t] 不会进行更新。

当 t+ans[t]-1=r 时，每执行一次 while r 都会加 1，因为 r 最大为 n。所以 while 最多执行 n 次。

故复杂度为 $O(n)$。

Z 函数(扩展 KMP)

一个字符串的 Z 函数是一个长度为 $n$ 的数组，其中 $z[i]=lcp(s[1:n],s[i:n])$。

求解 Z 函数的方法与 Manacher 类似。

维护一个最靠右的前缀 lcp $s[l:r]$。对于从 x 直接从 $z[x-l+1]$ 开始匹配即可。

代码：

1
2
3
4
5

if(i<=r)
	z[i]=min(z[i-l],r-i+1);
while(i+z[i]<n&&s[z[i]]==s[i+z[i]])++z[i];
if(i+z[i]-1>r)
	l=i,r=i+z[i]-1;

读者可以结合 manacher 部分自行分析。

字符串匹配

在 OI 学习中，最简单实用的字符串匹配方法是利用前缀函数或字符串 Hash 求匹配。另外也能用 z 函数做字符串匹配。

此外还有更高效的匹配算法，例如 Boyer-Moore 算法，当然博主也不会，博主肯定不会讲。

• Hash 方法

对于文本串的每个匹配串长度的的子串求出 Hash 值，和匹配串比较即可。

• 前缀函数方法

利用前缀函数快速跳 border 匹配。

• z 函数方法

用一个分隔符将匹配串和文本串连起来。求 $z$ 函数。通过 $z$ 函数的定义不难发现所有文本串位置 z 函数值为文本串长度的即为匹配位置

Lyndon 分解

一些定义：

Lyndon 串：字典序小于其所有后缀字典序的字符串。

Lyndon 分解：将一个字符串分解成若干依次字典序非严格递减的 Lyndon 串。

近似 Lyndon 串：一个字符串 $t=ww\cdots \overline w$，其中 $w$ 是一个 Lyndon 串。

可以用 Duval 算法来求 Lyndon 分解。(划记：它用到了贪心的思想，初赛可能会考。)

在算法流程中，我们将待分解字符串分成 $s1s2s3$ 相连的三个部分。其中 $s1$ 是一个 Lyndon 串，并且已经求出了它的 Lyndon 分解，$s2$ 是一个近似 Lyndon 串，$s3$ 是未处理的部分。

每次将 $s3$ 的首字符接到 $s2$ 后面，如果 $s2$ 不再是近似 Lyndon 串，就将 $s2$ 的一部分前缀接到 $s1$ 末尾。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

for(rg int i=1,j,k;i<=n;)
{
	j=i;k=i+1;
	while(k<=n&&s[j]<=s[k])
	{
		if(s[j]<s[k])j=i;
		else j++;
		k++;
	}
	while(i<=j)
	{
		ans^=(i+k-j-1);
		i+=k-j;
	}
}

可以证明复杂度是 $O(n)$ 的。

最小表示法

字符串 $s$ 的最小表示为与 $s$ 循环同构的所有字符串中字典序最小的字符串。

对于长度为 $n$ 的串 $s$，可以用 Lyndon 分解求出最小表示法。

对 $ss$ 进行 Lyndon 分解，找到垮过这两个串的 Lyndon 串的首字母，从它开始之后 $n$ 个数就是 $s$ 的最小表示法。

Trie

字典树 Trie，是一种数据结构。

OI wiki 上的图：

AC 自动机(ACAM)

多匹配串匹配：

给定 $n$个模式串 $s_i$ 和一个文本串 $t$，求有多少个不同的模式串在文本串里出现过。

可以先将这 $n$ 个模式串丢到 trie 上，现在问题变为我们要像构造前缀函数一样构造出函数 $fail$，表示所有字符串与当前节点所代表的字符串的最长 border 所在节点，用 $fail$ 来跑匹配。

可以使用广搜来进行这一过程：

如果我们当前考虑到了一个节点，那么它的 $fail$ 应该指向它的父亲的 $fail$ 连出相同字符边的节点。然后依次进行广搜即可。需要注意如果一个点没有相应字符的边，则将它连到它的 $fail$ 的相应字符边。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

void get_nxt()
{
	queue<int> q;
	for(int i=0;i<=25;i++)
		if(e[0].a[i])e[e[0].a[i]].nxt=0,q.push(e[0].a[i]);
	while(!q.empty())
	{
		int now=q.front();q.pop();
		for(int i=0;i<=25;i++)
		{
			if(e[now].a[i])
			{
				e[e[now].a[i]].nxt=e[e[now].nxt].a[i];
				q.push(e[now].a[i]);
			}
			else e[now].a[i]=e[e[now].nxt].a[i];
		}
	}
}

回文自动机(PAM)

AC 自动机也由转移边和 fail 指针构成。

在回文自动机上每走一条转移边表示在字符串两边同时加上一个字符。

回文自动机有两个根，一个根表示奇数回文串，一个根表示偶数回文串，分别命名奇根偶根，一开始偶根的 $fail$ 指针指向奇根。

构建方法：

考虑增量法构建。

每次从上一次插入到的点不停跳 $fa$ 满足条件的位置然后将新点连上去即可。简单易懂。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

int getfa(int p,int now)
{
    while(s[now]!=s[now-e[p].len-1])p=e[p].fa;
    return p;
}
void add(int x,int now)
{
    int p=getfa(las,now);
    if(!e[p].ch[x])
    {
        e[++tot].len=e[p].len+2;
        int t=getfa(e[p].fa,now);
        e[tot].fa=e[t].ch[x];
        e[tot].num=e[e[tot].fa].num+1;
        e[p].ch[x]=tot;
    }
    las=e[p].ch[x];
}

序列自动机

在这个自动机上从源点到每一个节点都是一个原串子序列。

构建方法：

考虑暴力：每次遍历一遍这个自动机，将没有当前值的转移边的节点向新节点连一条边这样是 $O(n)-O(1)$。

用平衡树来优化这一过程可以 $O(\log_2n)-O(\log_2n)$。

后缀数组

后缀数组 $sa$ 表示字符串每个排名的后缀的首字母位置，可以通过后缀排序求解。后缀排序可以用 DC3 或 SA-IS 做到 $O(n)$。或可以通过倍增算法 + 基数排序做到 $O(n\log_2n)$。一般在 OI 比赛中，我们主要采用后面的算法。

• 用 $sa$ 求 $height$

记 $height_i$ 表示排名为 $i-1$ 与排名为 $i$ 的 $lcp$ 长度。它可以通过 $sa$ 快速求出：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

void geth()
{
	for(int i=1;i<=n;i++)
		rk[sa[i]]=i;
	int k=0;
	for(int i=1;i<=n;i++)
	{
		if(rk[i]==1)continue;
		if(k)--k;
		int j=sa[rk[i]-1];
		while(i+k<=n&&j+k<=n&&s[i+k]==s[j+k])++k;
		h[rk[i]]=k;
	}
}

后缀自动机

考虑增量法构建。

每次分三种情况讨论。

因为这个比较难，看我的博客不一定能看懂，所以还是推荐去看专门讲这个的博客。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

void add(int x)
{
	int p=las;int np=las=++tot;f[tot]=1;
	e[np].len=e[p].len+1;
	for(;p&&!e[p].ch[x];p=e[p].fa)e[p].ch[x]=np;
	if(!p)e[np].fa=1;
	else
	{
		int q=e[p].ch[x];
		if(e[q].len==e[p].len+1)e[np].fa=q;
		else
		{
			int nq=++tot;
			e[nq]=e[q];
			e[nq].len=e[p].len+1;
			e[q].fa=e[np].fa=nq;
			for(;p&&e[p].ch[x]==q;p=e[p].fa)e[p].ch[x]=nq;
		}
	}

}