字符串

content: 字符串有关的标准库,KMP算法(寻找子串的高效算法,在 文本串s 中快速寻找 模式串p 的一种算法),Z算法,字典树,Manacher算法,后缀数组
[TOC]
标准库
C 标准库
C 标准库操作字符数组。
char[]
/const char*
printf("%s", s)
:用%s
来输出一个字符串(字符数组)。scanf("%s", &s)
:用%s
来读入一个字符串(字符数组)。sscanf(const char *__source, const char *__format, ...)
:从字符串__source
里读取变量,比如sscanf(str,"%d",&a)
。sprintf(char *__stream, const char *__format, ...)
:将__format
字符串里的内容输出到__stream
中,比如sprintf(str,"%d",i)
。strlen(const char *str)
:返回从str[0]
开始直到'\0'
的字符数。注意,未开启 O2 优化时,该操作写在循环条件中复杂度是的。
strcmp(const char *str1, const char *str2)
:按照字典序比较str1 str2
若str1
字典序小返回负值,两者一样返回0
,str1
字典序更大则返回正值。请注意,不要简单的认为返回值只有0
、1
、-1
三种,在不同平台下的返回值都遵循正负,但并非都是0
、1
、-1
。strcpy(char *str, const char *src)
: 把src
中的字符复制到str
中,str
src
均为字符数组头指针,返回值为str
包含空终止符号'\0'
。strncpy(char *str, const char *src, int cnt)
:复制至多cnt
个字符到str
中,若src
终止而数量未达cnt
则写入空字符到str
直至写入总共cnt
个字符。strcat(char *str1, const char *str2)
: 将str2
接到str1
的结尾,用*str2
替换str1
末尾的'\0'
返回str1
。strstr(char *str1, const char *str2)
:若str2
是str1
的子串,则返回str2
在str1
的首次出现的地址;如果str2
不是str1
的子串,则返回NULL
。strchr(const char *str, int c)
:找到在字符串str
中第一次出现字符c
的位置,并返回这个位置的地址。如果未找到该字符则返回NULL
。strrchr(const char *str, char c)
:找到在字符串str
中最后一次出现字符c
的位置,并返回这个位置的地址。如果未找到该字符则返回NULL
。
C++ 标准库
C++ 标准库操作字符串对象,同时也提供对字符数组的兼容。
std::string
- 重载了赋值运算符
+
,当+
两边是string/char/char[]/const char*
类型时,可以将这两个变量连接,返回连接后的字符串(string
)。 - 赋值运算符
=
右侧可以是const string/string/const char*/char*
。 - 访问运算符
[cur]
返回cur
位置的引用。 - 访问函数
data()/c_str()
返回一个const char*
指针,内容与该string
相同。 - 容量函数
size()
返回字符串字符个数。 find(ch, start = 0)
查找并返回从start
开始的字符ch
的位置;rfind(ch)
从末尾开始,查找并返回第一个找到的字符ch
的位置(皆从0
开始)(如果查找不到,返回-1
)。substr(start, len)
可以从字符串的start
(从0
开始)截取一个长度为len
的字符串(缺省len
时代码截取到字符串末尾)。append(s)
将s
添加到字符串末尾。append(s, pos, n)
将字符串s
中,从pos
开始的n
个字符连接到当前字符串结尾。replace(pos, n, s)
删除从pos
开始的n
个字符,然后在pos
处插入串s
。erase(pos, n)
删除从pos
开始的n
个字符。insert(pos, s)
在pos
位置插入字符串s
。std::string
重载了比较逻辑运算符,复杂度是 O(N) 的。
KMP算法
设两个字符串的长度分别是 n 和 m,则暴力匹配的最坏时间复杂度是 O(nm)。
暴力解法:
1 | int i = 0, j = 0; |
每次匹配失败时候,i 都要回溯,同时 j 置零。
分析算法
KMP算法引入 PMT(Partial Match Table,部分匹配表),能让 j 被赋予一个合适的值。
假设 文本串为 abababcabaa
,模式串为
ababcabaa
j 应该被赋予多少值,是只与模式串自身有关的。每个模式串,都对应着一张PMT,比如:
模式串 ababcabaa
对应的PMT如下:
pmt[i]
就是,从 p[0] 往后数,同时从 p[i]
往前数相同的位数,在保证前后缀相同的情况下,最多能数多少位。(但要小于p的长度)
专业点说,它是 真前缀 与 真后缀 的集合的中,最长元素的长度。
实例说明:
在暴力匹配中的情形:


遇到不同的字母,暴力选择将 j 前移,但是观察可知,前面 abab
匹配成功,它的前缀和后缀有重叠部分
'ab',我们可以将这个与前缀相同的后缀利用起来得到,在第二张图中,pmt[4] =
2,当遇到 这种不匹配的情况时,j
的变化为:j = ptm[4] = ptm[i-1]
。
再举个例子:
发生失配时,我们可以直接令
j = pmt[i-1]
(也就是符合条件的最长前缀所紧接着的下一位)。
代码过程为:
1 | for(int i = 0, j = 0; i<s.length(); i++) |
很多文章中会使用next
数组,即把PMT整体向右移一位(特别地,令next[0]=-1
),表示在每一位失配时应跳转到的索引。也就是说,失配时,按照i -> next[i] -> next[next[i]] -> ...
的顺序跳转。其实原理和实现都是差不多的。
求PMT数组
如果暴力求解时间复杂度 pmt[0] = 0
,而之后的每一位则可以通过在匹配过程中记录 j
值得到。
还是以下面的模式串为例:


匹配失败,则pmt[1] = -1+1 = 0
,i指针右移,接下来匹配成功,pmt[2] = 1
,然后两个指针都右移


继续匹配成功,j指针右移,pmt[3] = 2
,下一位失配,因为前面的
pmt
已经算出来了,我们可以像文本串匹配时那样使用它。pmt[2-1]
即pmt[1]
等于0,所以退回到开头。


j指针已经到了开头,仍未匹配成功,所以不再移动,pmt[4]=j=0
。接下来也按这种方法操作


最后一位出现失配,这次我们先令j=pmt[j-1]=1
,再次匹配,匹配成功,j指针右移一位,pmt[i]=j=1
。自此,我们通过一趟自我匹配,求出了PMT。
代码:
1 | //pmt[0] = 0 |
例题
题目描述
给出两个字符串 s1 和 s2,若 s2 的区间[l, r]子串与 s2 完全相同,则称 s2 在 s1 中出现了,其出现位置为 l。 现在请你求出 s2 在 s1 中所有出现的位置。
定义一个字符串s 的 border 为s 的一个非s本身的子串 t,满足 t 既是 s 的前缀,又是 s 的后缀。 对于s2,你还需要求出对于其每个前缀 s' 的最长 border t' 的长度。
输入格式
第一行为一个字符串,即为 s1。 第二行为一个字符串,即为 s2。
输出格式
首先输出若干行,每行一个整数,按从小到大的顺序输出 s2 在 s1 中出现的位置。 最后一行输出 ∣s2∣ 个整数,第 i 个整数表示 s2 的长度为2 的前缀的最长 border 长度。
代码
1 |
|
上面的算法只能称为 MP算法,真正的KMP算法,使用 nextval数组
1 |
|
Z 算法
Z算法(Z-Algorithm)是一种字符串算法,在国内也常常被叫做拓展KMP算法。
KMP算法 的核心就是那张 部分匹配表,其实它被称为
前缀函数,记作
而 Z算法的核心 是 Z函数,它的定义与
例如,设有字符串aabcaabcaaaab
,那么它的Z函数值如下表所示:

算法过程
设
我们从左往右枚举下标
如果
,说明我们已经完全越过了上一个 Z-Box,任何一个新的Z-Box 的 r 都会更大,这时 我们直接逐个比较,暴力计算 的值。计算完成后,如果 ,则更新 和 。 1
2
3
4
5
6if(i > r)
{
while(i+z[i] < n && s[z[i]] == s[i+z[i]])
z[i]++;
l = i, r = i+z[i]-1;
}如果
,此时已经知道了 与 是相等的,因此 与 也是相等的。所以我们考虑 ,说明从 开始匹配 和 从 开始匹配是 一样的——匹配一定会在离开 Z-Box 前停止。即, 。 1
2else if(z[i-l] < r-i+1)
z[i] = z[i-l];如果
,说明整个 Z-Box 的剩余部分都可以匹配,但后面的情况我们不清楚,所以不能说 。但我们知道 至少有 ,接下来我们暴力计算 Z-Box 还能向后延长多少即可 1
2
3
4
5
6
7else
{
z[i] = r-i+1;
while(i+z[i] < n && s[z[i]] == s[i+z[i]])
z[i]++;
l = i, r = i+z[i]-1;
}
综合分析可以发现 第一种和第三种情况可以合并,最终得到:
1 | for(int i = 1, l = 0, r = 0; i<n; i++) |
时间复杂度:O(N)
简单应用
给出字符串 a, b,求 a 的每个后缀与 b 的LCP
设 @ 为字符集外字符,求 b+@+a 的 Z 函数,则 a 的后缀 a[i..] 与 b 的 LCP 为 Z(|b|+1+i)。
给出文本串 s 和 模式串 p,求 p 在 s 中的所有出现位置
这是 KMP 和字符串哈希的经典题目,但也可以用 Z 算法。设 @ 为 字符集外字符,求 p+@+s 的Z 函数,则每个Z(i) = |p| 都对应 p 在 s 中的一次出现。
求 s 的所有 border
虽然是 纯KMP 题,但也可以用 Z算法。求 s 的 Z 函数。对于每一个 i,如果 i+Z(i) = |s|,说明这个 Z-Box 对应一个 border。(注:与 KMP 不同,这里只是求所有 border,不是求所有的向前 border)
求 s 的每个前缀出现的次数
求 s 的 Z 函数。对于每一个 i,如果 Z(i) 不等于 0,说明长度为 Z(i), Z(i)-1,..., 1 的前缀在次数各出现了一次,所以求一个后缀和即可。在这个问题一般令 Z(0) = |s|。
1 | for(int i = n+1; i<2*n+1; i++) |
Manacher算法
介绍
Manacher算法,俗称 马拉车,是一种与 回文子串 有关的算法。
回文串根据长度的奇偶性可以分为 奇回文串 和 偶回文串 两种。奇回文串 通常比偶回文串好处理,因为 它有一个中心,而且可以从中心往两边同时拓展。
对字符串进行预处理可以用处理 回文串的方法处理 偶回文串。方法是:在每队相邻字符和字符串的两端加入一个 字符集外字符(这里设为 @),例如 abbab 变成 @a@b@b@a@b@。这样处理后,原来的 bab 变成了 @b@a@b@,原来的 abba 变成了 @a@b@b@a@。可以发现,原来的 奇回文子串 会变成以普通字符为中心的 奇回文子串;原来的 偶回文子串 会变成以 @为中心的 奇回文子串。
对于一个字符串 s,设 d[i] 表示以 s[i] 为中心的 奇回文子串
的数量。很明显,d[i] 个回文子串 的长度分别为 1, 3, ..., 2d[i]-1。如果 s
是由 t 预处理得到的,那么这些回文子串对应 t 中对应位置的
Manacher算法的作用,就是 O(n) 地求出 这个 d 数组。
分析
Manacher算法其实和 Z算法
的流程非常类似。从左往右枚举
如果
,则直接暴击计算 d[i],同时更新 l 和 r。 1
2
3
4
5
6if(i > r)
{
while(i-d[i]>=0 && i+d[i]<n && s[i-d[i]] == s[i+d[i]])
d[i]++;
l = i-d[i]+1, r = i+d[i]-1;
}如果
,找到 关于 中心的对称点 ,这时如果以 为中心的最长奇回文串的左边界大于 ,则直接令 。这是因为,在 的范围内,关于中心点对称的子串一定是相等的。 1
2
3
4
5//i<= r int j = l+r-i;
else if(j - d[j] >= l) //即 j-d[j]+1 > l
{
d[i] = d[j];
}如果以
为中心的最长奇回文串的左边界小于等于 ,那么我们知道 至少有 (或 ),但会不会更长还不清楚,所以要进行左右拓展,同时更新 和 。 1
2
3
4
5
6
7else
{
d[i] = j-l+1;
while(i-d[i] >= 0 && i+d[i] < n && s[i-d[i]] == s[i+d[i]])
d[i]++;
l = i-d[i]+1, r = i+d[i]-1;
}
综合分析,得到以下代码:
1 | for(int i = 0, l = 0, r = -1; i<n; i++) |
时间复杂度为:
字典树
字典树(Trie) 是一种比较简单的数据结构,也叫
前缀树,用来存储和查询字符串。例如:water
,wish
,win
,tie
,tired
这几个单词可以用以下方式存储:
其中每个字符占据一个节点,拥有相同前缀的字符串可以公用部分节点。起点是特殊点(设为1号点),不存储字符。建树的代码如下:
1 | struct trie |
应用
检索字符串
字典树最基础的应用——查找一个字符串是否在「字典」中出现过。
给你 n 个名字串,然后进行 m 次点名,每次你需要回答「名字不存在」、「第一次点到这个名字」、「已经点过这个名字」之一。
分析:对所有名字建 trie,再在 trie 中查询字符串是否存在、是否已经点过名,第一次点名时标记为点过名。
题解:
1 |
|
维护异或极值
将数的二进制表示看作一个字符串,就可以建出字符集为 {0, 1} 的 trie 树
给你一棵带边权的树,求 (u, v) 使得 u 到 v 的路径上的边权异或和最大,输出这个最大值。
点数不超过
分析:
指定一个根 root,用 T(u, v) 表示 u 和 v 之间路径的边权异或和,那么
那么,如果将所有 T(root, u) 插入到一棵 trie 中,就可以对每个 T(root, u) 快速求出和它异或和最大的 T(root, v):从 trie 的根开始,如果能向和 T(root, u) 的当前位不同的子树走,就向那边走,否则没有选择。
贪心的正确性:如果这么走,这一位为 1;如果不这么走,这一位就会为 0。而高位是需要优先尽量大的。
维护异或和
01-trie 是指 字符集为 {0, 1} 的 trie。01-trie 可以用来维护一些数字的异或和,支持修改(删除+重新插入),和全局加一(即:让其所维护所有数值递增 1,其本质上是一种修改操作)
如果要维护异或和,需要按值从低位到高位建立 trie。
一个约定:文中说当前节点 往上 指当前节点到根这条路径,当前节点 往下 指当前节点的子树。
插入 & 删除
如果要维护 异或和,我们 只需要 知道某一位上 0 和 1 个数的 奇偶性 即可,也就是对于数字 1 来说,当且仅当这一位上 数字 1 的个数为奇数时,这一位上的数字 才是 1。
注意:如果只是维护 异或和,我们只需要知道某一位上 1 的数量即可,而不需要知道 trie 到底维护了哪些数字。
对于每一个节点,我们需要记录以下三个量:
ch[o][0/1]
指节点o
的两个儿子,ch[o][0]
指下一位是0
,同理ch[o][1]
指下一位是1
。w[o]
指节点o
到其父亲节点这条边上数值的数量(权值)。每插入一个数字x
,x
二进制拆分后在 trie 上 路径的权值都会+1
。xorv[o]
指以o
为根的子树维护的异或和。
具体维护节点的代码如下:
1 | void maintain(int o) |
插入和删除的代码非常相似。在代码中:MAXH
指 trie
的深度,也就是让每个叶子节点到根节点的距离为
MAXH
。对于一些比较小的值,可能有时候不需要建立那么深(例如:如果插入数字
4
,分解为二进制后为 100
,从根除插入
001
这三位即可),但是我们强制插入 MAXH
位,这样做是为了便于 全局 +1
时处理进位。例如:如果原数字是
3
(11
),递增之后变成4
(100
),如果插入
3
时只插入 2
位,那这里的进位就没了。
插入和删除,只需要修改叶子节点的 w[]
即可,在回溯的过程中一路维护即可。
1 | namespace trie{ |
全局加一
让这棵 trie 中所有的数值 +1
。
设 trie 中维护的数值有 +1
后 其中维护的值应该变成
1 | void addall(int o) |
对应 trie 的操作,其实就是交换其左右儿子,顺着
交换后 的 0
边往下递归操作即可。
回顾一下 w[o]
的定义:w[o]
指节点
o
到其父亲节点这条边上数值的数量(权值)。
有没有感觉这个定义有点怪呢?如果在父亲结点存储到两个儿子的这条边的边权也许会更接近于习惯。但是在这里,在交换左右儿子的时候,在儿子结点存储到父亲这条边的距离,显然更加方便。
01-trie 合并
将上述两个 01-trie 进行合并,同时维护的信息。
实现分三种情况:
如果
a
没有这个位置上的结点,新合并的结点就是b
如果
b
没有这个位置上的结点,新合并的结点就是a
如果
a
,b
都存在,那就把b
的信息合并到a
上,新合并的结点就是a
,然后递归操作处理 a 的左右儿子。提示:如果需要的合并是将 a,b 合并到一棵新树上,这里可以新建结点,然后合并到这个新结点上,这里的代码实现仅仅是将 b 的信息合并到 a 上。
实现:
1 | int merge(int a, int b) { |
其实 trie 都可以合并,换句话说,trie 合并不仅仅限于 01-trie。
后缀数组
后缀数组(Suffix Array, SA)是解决很多与字符相关的问题的有力工具。它实际上就是把字符串所有 后缀 按 字典序 排序后得到的数组。
显然,直接使用 std::sort
函数 时间复杂度
首先,把字符串的长度扩充一倍,保证往后填充的字符比所有已有的字符都小(记为 0)。注意,这样填充后并不会影响原先 两个后缀的大小相对关系。
设
我们可以轻松地求出
如果我们已经知道了
原理:对于两个等长的字符串 s 和 t,如果 s 的字典序小于 t,那么要么 s 的前半段的字典序小于 t 的后半段的字段序。
所以我们可以从
在实际实现过程中,我们不需要求出
1 | char s[MAXN]; |
降低复杂度:计数排序 代替 std::sort
,时间复杂度
1 | char s[MAXN]; |
常数优化,在 n 较大的情况下能更快速
我们每次需要遍历 max(n, 128) 个数,实际上是很浪费的。注意到,我们每次都计算出了一个 ,它其实就是 cnt 的值域。实际上,除了第一次循环后值域可能减小,cnt 的值域都是逐渐增长到 n 的。而且当它增长到 n 时,说明每个子串的 rk 互不相同,数组已经不会再有变化了,这时可以提前退出。
1 | char s[MAXN]; |
洛谷上与后缀数组有关的题目:
- P3805 【模板】后缀数组
- P3806 【模板】后缀数组 2
- P3807 【模板】后缀数组 3
- P3808 【模板】后缀数组 4
- P3809 【模板】后缀数组 5
- P3375 【模板】KMP字符串匹配
- P3376 【模板】AC自动机(字符串多模式匹配)
- P3803 【模板】广义后缀自动机
- P3804 【模板】广义后缀数组
- P3802 【模板】SAM模板
后缀的最长公共前缀
我们令
首先,求 height 数组,一个结论很重要:
设
,则 恒成立
分析结论:比如某个后缀为 cxz,它的上一个后缀为 cxy(字典序),则 LCP
就是 cx(长度记为
h[i-1])。现在考察它下一个后缀(编号意义下)xz,我们已经知道字符串存在一个后缀
xy,字典序比 xz 小,而且它与 xz 的 LCP 为 x(长度为 h[i-1]-1),则有
利用这个结论,O(n) 求出 height 数组
1 | void init_ht(int n) |
解决的问题:
- 按字典序遍历所有本质不同的子串。只需要遍历
的前缀,但是跳过前 height[i] 个,因为这 height[i] 个前缀是与 sa[i-1] 共有的,之前一定已经被遍历过。按此道理,也可以知道字符串本质不同的字符串数量为 。 - 可以求两个子串的 LCP。显然设两个子串为
。则它们的最长公共前缀为 min(|s1|, |s2|, lcp(sa[l1], sa[l2]))。所以我们只需要求两个后缀的 LCP,而很容易发现这正是 min(height[k]) (l1 <= k <= l2)
题
串联所有单词的子串
给定一个字符串 s
和一个字符串数组
words
。 words
中所有字符串
长度相同。
s
中的 串联子串 是指一个包含
words
中所有字符串以任意顺序排列连接起来的子串。
- 例如,如果
words = ["ab","cd","ef"]
, 那么"abcdef"
,"abefcd"
,"cdabef"
,"cdefab"
,"efabcd"
, 和"efcdab"
都是串联子串。"acdbef"
不是串联子串,因为他不是任何words
排列的连接。
返回所有串联字串在 s
中的开始索引。你可以以
任意顺序 返回答案。
示例 1:
1 | 输入:s = "barfoothefoobarman", words = ["foo","bar"] |
示例 2:
1 | 输入:s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"] |
示例 3:
1 | 输入:s = "barfoofoobarthefoobarman", words = ["bar","foo","the"] |
提示:
1 <= s.length <= 104
1 <= words.length <= 5000
1 <= words[i].length <= 30
words[i]
和s
由小写英文字母组成
分析
暴力枚举+哈希映射
首先,最直接的思路,判断每个子串是否符合,符合就把下标保存下来,最后返回即可。怎么判断子串是否符合?这也是这个题的难点了,由于子串包含的单词顺序并不需要固定,如果是两个单词 A,B,我们只需要判断子串是否是 AB 或者 BA 即可。如果是三个单词 A,B,C 也还好,只需要判断子串是否是 ABC,或者 ACB,BAC,BCA,CAB,CBA 就可以了,但如果更多单词呢?那就崩溃了。
用两个 HashMap 来解决。首先,我们把所有的单词存到 HashMap 里,key 直接存单词,value 存单词出现的个数(因为给出的单词可能会有重复的,所以可能是 1 或 2 或者其他)。然后扫描子串的单词,如果当前扫描的单词在之前的 HashMap 中,就把该单词存到新的 HashMap 中,并判断新的 HashMap 中该单词的 value 是不是大于之前的 HashMap 该单词的 value ,如果大了,就代表该子串不是我们要找的,接着判断下一个子串就可以了。如果不大于,那么我们接着判断下一个单词的情况。子串扫描结束,如果子串的全部单词都符合,那么该子串就是我们找的其中一个。
1 | class Solution { |
- 标题: 字符串
- 作者: 卡布叻_米菲
- 创建于 : 2023-04-11 20:30:00
- 更新于 : 2024-02-08 13:08:49
- 链接: https://carolinebaby.github.io/2023/04/11/字符串/
- 版权声明: 本文章采用 CC BY-NC-SA 4.0 进行许可。
预览: