定义

字符串

对于一个字符串 \(S\) ， \(S\) 由 \(n\) 个字符组成，其中 \(n\) 是 \(S\) 的长度，表示为 \(|S|\) 。

子串

从一个字符串 \(S\) 中取出连续的一段 \(T\) ，则 \(T\) 为 \(S\) 的子串。

子序列

从一个字符串 \(S\) 中顺序取出一些字符，组成的新的字符串就是 \(S\) 的子序列。

前缀

从 \(S\) 的第一个字符开始取的子串。

后缀

以 \(S\) 的最后一个字符结束的子串。

回文串

正着和倒着都一样的字符串。

周期

我们定义，如果一个字符串是以一个或者一个以上的长度为 \(k\) 的重复字符串所连接成的，那么这个字符串就叫做周期为 \(k\) 的串。

\(\text C++\) 标准库

• s.c_str()/s.data() 返回一个指针，内容就是原来的字符串。
• s.size() 返回字符个数。
• s.find(c, begin) 查找并返回从 begin 开始的 c 的位置。
• s.substr(begin,len) 从 begin 开始截取一段长度为 len 的字符。
• s.append(s',pos,len) 将 s' 中从 pos 开始的 len 个字符接到 s 的末尾。
• s.replace(pos,n,s') 将 s 中从 pos 开始的长为 n 的子串替换成 s' 。
• s.erase(pos,len) 删除从 pos 开始的 len 个字符。
• s.insert(pos,s') 在 pos 处插入 s' 。

哈希

定义

哈希其实就是一个映射，它通过一个函数将一些抽象的东西变成直观的数字，方便我们去比较信息。

字符串哈希

就是把字符串通过映射变成一个数，方便比较。一般把字符串看成一个多位数，进制取一个质数，然后选择一个大模数。

性质

• 哈希值不同的原来一定不同。
• 哈希值相同的原来不一定相同。

如果原来不同但是哈希值相同，我们称此为哈希冲突。

哈希冲突

我们设哈希后字符串取值范围为 \(mod\) ，字符串数量为 \(n\) ，则哈希冲突概率为：

证明：

先算哈希不冲突的概率为：

然后根据泰勒公式：

当 \(x\) 非常小时， \(\exp(x)\) 趋近于 \(x+1\) 。

所以之前的式子就可以写成：

所以哈希冲突概率为：

那么，我们在实际写题的时候又应该如何避免呢？

双哈希

顾名思义，就是对于一个字符串分别设置两个函数，判断是否相等就看两个哈希值是否都相等即可。

例题

P3370 【模板】字符串哈希

板子题没啥好说的。

P2757 [国家集训队] 等差子序列 Problem - 452F - Codeforces 双倍经验

题解

转化题意，就是在序列中找到一个位置 \(i\) ，对于 \(a_i\) 找到一个 \(t\) 使得 \(a_i-t\) 和 \(a_i+t\) 分别在 \(a_i\) 的两侧。首先可以想到去枚举中间数，暴力去找。

如何优化呢？假设现在有一个数组 \(b\) 。当我们枚举中间数，左侧的全部标记为1。对于枚举的数 \(x\) ，我们需要去判断每一个可能的 \(t\) 是否有 \(x-t\) 和 \(x+t\) 在数组 \(b\) 的值是否相等。这就像在序列中抓出一段子串去 判断是否为回文串 ，然后还要支持单点修改。

到这里我们就用线段树做就行了。维护正序倒序两种哈希值，单点修改就做完了。

（由于没写所以代码就不放啦喵）

P3449 [POI2006] PAL-Palindromes

题解

先去寻找题目性质。首先能发现输入的都是回文串！然后想一想如果两个串要组成大的回文串需要什么条件？

我们先假设有两个回文串 \(s\) 和 \(t\) ，我们假设 \(s\) 的最小周期是 \(c\) ，那么 \(s\) 可以表示成 \(c^p\) 。如果 \(s\) 和 \(t\) 能够拼成回文串，那么 \(t\) 一定也能写成 \(c^q\) 的形式。所以当两个回文串的最小周期相同的时候就能够拼成回文串。

我们就开一个 map 记一下每个最小周期相同的个数然后就做完了。时间复杂度小于调和级数所以是 \(\Theta(n\log n)\) 。

代码

int n, m;
const int b1 = 133, b2 = 233, m1 = 1e9 + 7, m2 = 1e9 + 9;
ll h1[N], h2[N], s1[N], s2[N], ans;
char s[N];
map < pll , ll > mp;
pll aim;

pll geth(int l, int r){
    ll x1 = (h1[r] - h1[l - 1] * s1[r - l + 1] % m1) + m1; x1 %= m1;
    ll x2 = (h2[r] - h2[l - 1] * s2[r - l + 1] % m2) + m2; x2 %= m2;
    return mkp(x1, x2);
}
bool eq(pll x, pll y){
    return x.first == y.first and x.second == y.second;
}
bool chk(int len){
    for(int i = len + 1; i <= m; i += len)if(! eq(geth(i, i + len - 1), aim))return false;
    return true;
}

signed main(){
    n = rd(); s1[0] = s2[0] = 1;
    for(int i = 1; i < N; ++i)s1[i] = s1[i - 1] * b1 % m1, s2[i] = s2[i - 1] * b2 % m2;
    while(n--){
        m = rd(); scanf("%s", s + 1);
        for(int i = 1; i <= m; ++i)h1[i] = (h1[i - 1] * b1 % m1 + s[i]) % m1, h2[i] = (h2[i - 1] * b2 % m2 + s[i]) % m2;
        for(int i = 1; i <= m; ++i)if(m % i == 0){
            aim = geth(1, i);
            if(chk(i)){ans += (mp[aim]++ << 1) + 1; break;}
        }
    }
    printf("%lld", ans);
    return 0;
}

KMP

介绍

KMP 算法是解决字符串中的匹配问题的高效算法。最基本的问题是给你一个文本串和模式串，让你求出模式串在匹配串中出现的位置、次数等。

匹配问题

关于这个问题其实有很多的做法。

1. 暴力做法：枚举文本串每个位置作为起点开始按位匹配，如果不行就换起点。
2. 哈希做法：预处理出文本串与模式串的哈希值然后 \(O(|S|)\) 比较。
3. KMP！

前言

虽然就一个模式串和一个匹配串的题看不出哈希和 KMP 的差距，但 KMP 的思想可以用于解决多模式串匹配串的题，这也就是学习 KMP 的意义。

字符串的 border

前言

border 是一个非常重要的概念，所以在介绍所有匹配的东西之前我们需要先了解 border 以及它的一些性质。

概念

如果字符串的一个真前缀和真后缀相等，那么我们称此为这个字符串的 border。

性质

周期有关

1. 如果一个前缀 \(s[1\dots i]\) 是 \(s\) 的 border，那么 \(|s|-i\) 是 \(s\) 的周期。
2. 若 \(p,q\) 都是 \(s\) 的周期，且 \(p+q≤|s|\) ，则 \(\gcd(p,q)\) 也是 \(s\) 的周期。

性质 1 很简单可以画图自证；

性质 2 证明：钦定 \(p<q\) ，设 \(d=q-p,n=|s|\) 。

• 对于 \(i\in[p+1,n]\) ，我们能发现 \(s[i]=s[i-p]=s[i-p+q]=s[i+d]\) ；
• 对于 \(i\in[1,n-q]\) ，我们同样能发现 \(s[i]=s[i+q]=s[i+q-p]=s[i+d]\) 。

\(\because p+q\le n,\therefore p\le n-q\) ，因此上述两种情况能够涵盖整个字符串，所以 \(d\) 也是 \(s\) 的一个周期，然后令 \(q=p,p=d\) 重复上面的过程（类似辗转相除法）就可以得到性质 2。

border 本身性质

1. 对于一个字符串 \(s\) ，它的所有长度 \(\ge\frac{|s|}{2}\) 的 border 的长度是等差序列。
2. 字符串的所有 border 组成 \(O(\log n)\) 个等差序列。

性质 3 证明：假设我们知道最大的 border 是 d，那么字符串的最小周期为 \(r=|s|-d\) 。因为 \(r\) 是最小的周期，那么 \(2r,3r,4r\dots\) 也就一定是周期，所以这些周期对应的 border \(d-r,d-2r,d-3r\dots\) 也就为等差序列。

性质 4 证明：首先对于长度 \(\ge\frac{|s|}{2}\) 的 border 我们可以性质 3 处理，这里只讨论其余的 border。假设现在剩下的 border 中最长的为 \(B\) （如图），而对于其他任意的 border \(A\) ，都有 \(A\) 是 \(B\) 的 border。至于原因可以根据定义推一推，下图已经画得很 不 清晰了。

所以又可以根据性质 3 又分出一些长度 \(\ge\frac{|B|}{2}\) 的 border，然后以此类推。因为每次 \(|B|\) 都至少减半，所以是 \(\log n\) 的。

例题： WC2016 论战捆竹竿

题解

考虑一个串不同的贡献就是这个串的长度减去 border，然后可以将题意转化为给你一些数，问你可以凑出多少不超过 \(w-n\) 的数。如果凑出 \(\bmod n\) 余 \(0\dots n\) 的数，那么每次加 \(n\) 就可以凑出新的数，所以可以想到同余最短路。如果直接暴力连边就是 \(O(n^2)\) 的复杂度，所以考虑优化。

因为 border 的性质是 \(O(\log n)\) 的等差序列，我们可以分开考虑每一个等差序列，然后在转移两个不同的等差序列。对于一个等差序列 \(A_i=x+d\times i\) ，他们在 \(\bmod x\) 的意义下可以分成 \(\gcd(x,d)\) 个环，读者可自行画图证明。对于每一个点 \(i\) 向 \((i+d)\%x\) 连边，然后就有了转移方程：

转移时可以单调队列维护 \(f_j-id_j\times d\) ，我们就选出环上最小的 \(f_i\) 以它为起点转移。

最后考虑两个等差序列之间如何转换。对于一个点 \(i\) ，我一定是从前面一个数加上了若干倍的 \(x'\) 后在 \(\bmod x\) 的意义下为 \(i\) 。然后就可以转化成 \(i\) 向 \((i+x')\%x\) 连边，转移就与上面的式子基本一模一样（就只是少了一个 \(x\) ）。

因为作者太菜了写不来所以就不放半成品了

前缀函数

在正式讲 KMP 前，我们需要学习前缀函数。

对于一个位置 \(i\) ， \(\pi(i)\) 表示 \(i\) 的前缀函数，而前缀函数记录的则是子串 \(s[1\dots i]\) 中 最长且相等 的真前缀与真后缀的长度，换句话说，前缀函数就是最大的 border。

举一个例子：若我现在有一个字符串 \(s=aabaaba\) ，则每一个位置对应的前缀函数 \(\pi\) 为：0，1，0，1，2，3，1。

如何去求前缀函数？

对于一个字符串，假设我们已经求出 \(\pi(1\dots i-1)\) ，那应该如何求出 \(\pi(i)\) 呢？

我们知道前缀函数是算的最长相等真前缀真后缀，所以我们可以先去比较 \(s[i]\) 与 \(s[\pi(i-1)+1]\) 的位置。因为 \(s[1\dots\pi(i-1)]=s[i-\pi(i-1)\dots i-1]\) ，如果它们的下一位相等，那么就可以直接更新 \(\pi(i)\) 。

那如果它们不同呢？我们可以记录一个 \(j\) ，初始为 \(i-1\) 。当上述情况不满足条件时，我们令 \(j=\pi[j]\) ，继续比较 \(s[1\dots\pi(j)]=s[i-\pi(j)\dots i-1]\) 。

具体的可以参考上面我画的图 （好丑） 。如果两个大的部分（ \(s[1\dots\pi(i-1)]，s[i-\pi(i-1)\dots i-1]\) ）相等，就只用比较下一位；如果发现不等（如图中字符 \(c\) 与 \(a\) 不等），那么就继续回跳前缀函数。然后容易看出图中四个小长方形对应位置的子串相等，如果 \(s[1\dots\pi(j)]=s[i-\pi(j)\dots i-1]\) 那么我们就找到了 \(\pi(i)\) 。

我们已经求出前缀函数，那么如何用前缀函数求解匹配问题呢？

KMP 算法

先放图qwq。

看完图我们能发现：这个流程与前面求前缀函数的过程非常类似。我们可以先求出模式串 \(t\) 的前缀函数，然后用类似求前缀函数的方法在匹配串 \(s\) 上扫一遍，如果对于当前的字符 \(s_i\) 与 \(t_{j+1}\) 不匹配，那么就从 \(j+1\) 往回跳。当指针 \(j\) 等于 \(|t|\) 时说明找到了 \(s\) 中一段子串能够匹配 \(t\) 。

代码（我远古时期写的板子）

int n, m, j, k[N];
char a[N], b[N];
void solve(){
	cin >> a + 1;
	cin >> b + 1;
	n = strlen(a + 1); m = strlen(b + 1);
	FL(i, 2, m){
		while(j and b[i] != b[j + 1])j = k[j];
		if(b[i] == b[j + 1])j++;
		k[i] = j;
	}
	j = 0;
	FL(i, 1, n){
		while(j > 0 and a[i] != b[j + 1])j = k[j];
		if(a[i] == b[j + 1])j++;
		if(j == m){
			cout << i - m + 1 << '\n';
			j = k[j];
		}
	}
	FL(i, 1, m)cout << k[i] << ' ';
}

例题

USACO15FEB Censoring S

题解：

疑似板子？就是在匹配文本串时用栈代替数组，当找到一个匹配时就把这一段弹出去，然后维护一下前缀函数即可。

代码

int n, m, fail[N], j, top, cur[N];
char a[N], b[N], st[N];

signed main(){
    // fileio(fil);
    scanf("%s %s", a + 1, b + 1); n = strlen(a + 1), m = strlen(b + 1);
    for(int i = 2; i <= m; ++i){
        while(j and b[i] ^ b[j + 1])j = fail[j];
        if(b[i] == b[j + 1])++j; fail[i] = j;
    }
    j = 0;
    for(int i = 1; i <= n; ++i){
        st[++top] = a[i];
        while(j and st[top] ^ b[j + 1])j = fail[j];
        if(st[top] == b[j + 1])++j;
        if(j == m)top -= m, j = cur[top];
        cur[top] = j;
    }
    for(int i = 1; i <= top; ++i)putchar(st[i]);
    return 0;
}

P4391 BOI2009 Radio Transmission 无线传输

题解

找周期就直接用长度减去 \(\pi(|S|)\) 即可。

trie 树

介绍

顾名思义就是一颗 朴实无华 的树。有一个根，从根往下有一些子树，从根到某个点的路径就是一个字符串。

这里引用了 OI-wiki 上的一张图，以便读者能更直观地理解 trie 树。比如 12 号点就代表了一个字符串 \(\text caa\) 。

这里先给出 trie 的板子。

int T, n, m;
char s[N];
map < char, int > mp;
struct trie{
	int cnt, nex[N][63], ext[N];
	void ins(char *s, int l){
		int p = 0;
		FL(i, 1, l){
			int ch = mp[s[i]];
			if(! nex[p][ch])nex[p][ch] = ++cnt;
			p = nex[p][ch]; ext[p]++;
		}
	}
	int query(char *s, int l){
		int p = 0;
		FL(i, 1, l){
			int ch = mp[s[i]];
			if(! nex[p][ch])return 0;
			p = nex[p][ch];
		}
		return ext[p];
	}
	void clear(){
		FL(i, 0, cnt){
			ext[i] = 0;
			FL(j, 0, 62)nex[i][j] = 0;
		}cnt = 0;
	}
}t;
void init(){
	int tot = 0;
	for(char i = 'a'; i <= 'z'; i++)mp[i] = ++tot;
	for(char i = 'A'; i <= 'Z'; i++)mp[i] = ++tot;
	for(char i = '0'; i <= '9'; i++)mp[i] = ++tot;
}

那么 trie 树又有什么用呢？

应用

1. 查询字符串。直接沿着树边走就行，如果走到空节点就说明不存在这个字符串。
2. 与 KMP 合体变成 ACAM！这个会在其他博客中讲。
3. 01 trie

这里稍微讲一下 01 trie。

01 trie

01 trie 是一种特殊的 trie，它维护了一些由 0 和 1 组成的字符串。然后对于任意整数我们都可以把它写成二进制，这样我们就能够用 01 trie 维护一些数了，而且把这些数丢进 01 trie 中它会自动排好序，然后你也许会意识到它（01 trie）就类似一颗平衡树。然而作者数据结构学得西撇，所以不在此讲有关维护 01 trie 的内容，对于字符串只要知道 trie 能够查询字符串也许就行了。（逃

例题

P2580 于是他错误的点名开始了

题解

就是普通的在 trie 上做插入操作，然后每次查询后维护一下字符串是否被第一次询问即可。

P4551 最长异或路径

题解

首先要知道 \(\oplus\) 的性质。比如一些东西异或偶数次就会抵消。然后问题是找树上一条异或和最大的路，我们可以先求出从根节点到每个点的异或和 \(d_i\) ，然后对于任意两点 \(u,v\) 的路径异或和就能表示为 \(d_u\oplus d_v\) 。我们就可以把所有 \(d_i\) 扔进一颗 01 trie 里，然后枚举每一个点，贪心去找最大异或。因为高位更大数值一定更大所以贪心是正确的，然后就做完了。

代码

int n, hd[N], cnt, dis[N], trie[N << 4][2], cnt_t = 1, ans;
bool ed[N << 4];
struct edge{int nxt, to, d;}e[N << 1];
void add(int x, int y, int z){e[++cnt] = (edge){hd[x], y, z}; hd[x] = cnt;}
void dfs(int u, int fa)
{
	for(int i = hd[u]; i; i = e[i].nxt)
	{
		int v = e[i].to, val = e[i].d;
		if(v == fa)continue;
		dis[v] = dis[u] xor val; dfs(v, u);
	}
}
void ins(int x)
{
	int k = 1;
	for(int i = 31; i > ~ i; i--)
	{
		int ret = (x >> i) & 1;
		if(!trie[k][ret])trie[k][ret] = ++cnt_t;
		k = trie[k][ret];
	}
	ed[k] = true;
}
int find(int x)
{
	int k = 1, ans = 0;
	for(int i = 31; i > ~ i; i--)
	{
		int ret = (x >> i) & 1;
		if(trie[k][ret xor 1])k = trie[k][ret xor 1], ans += 1 << i;
		else k = trie[k][ret];
	}
	return ans;
}
signed main()
{
	cin >> n;
	for(int i = 1, x, y, z; i < n; i++)
	{
		scanf("%d %d %d", &x, &y, &z);
		add(x, y, z); add(y, x, z);
	}
	dfs(1, 0);
	for(int i = 1; i <= n; i++)ins(dis[i]);
	for(int i = 1; i <= n; i++)ans = max(ans, find(dis[i]));
	cout << ans; return 0;
}

最后

以上就是这篇博客的全部内容了，这篇博客以讲基础为主（hash、KMP、trie），加了一点稍难的题目。后面还会写三篇字符串的博客然后结束字符串所有内容，请敬请期待。

参考资料

border 的一些性质 - kymru - 博客园

字符串部分简介 - OI Wiki

【算法图文动画详解系列】KMP 字串匹配搜索算法-腾讯云开发者社区-腾讯云

Border / 回文 Border 理论小记 - Lgx_Q - 博客园