字符串
字符串是由字符按顺序排列形成的串结构。
在ACM中会用到两种字符串定义方式:
// C-style string
#define STR_LEN 100
char s1[STR_LEN];
// C++/STL-style string
#include <string>
std::string s2;
C风格字符串本质上就是字符数组;C++/STL风格字符串是将字符数组与其操作抽象集成形成的类,可以说本质上依旧是对字符数组进行操作。
字符串的常用操作
对于C风格字符串而言,所有的字符串操作函数被定义在头文件cstring
中,在使用时需要在程序中添加#include<cstring>
。
// Index
char a = s1[1];
// Get length -> O(n)
int b = strlen(s1);
// Compare
int c = strcmp(s1, s2);
// Memory set value
memset(s1, 0, sizeof(s1));
对于C++/STL风格的字符串而言,其字符串类定义在头文件string
中,在使用时需要在程序中添加#include<string>
。
// Index
char a = s1[1];
// Get length -> O(1)
int b = s1.length();
// Compare
bool c = s1 < s2;
大部分程序标准提供的操作函数,编译器提供的都是$$O(n)$$时间复杂度算法。
字符串匹配
字符串匹配就是在一个字符串中寻找另一个字符串的过程,字符串匹配在计算机领域有非常多的应用(搜索引擎、数据库等),其重要程度也不言而喻。
在如下例子中s1是s2的一个匹配,而s3不能匹配其他两个字符串:
s1 = "abc";
s2 = "aaabccc";
s3 = "ac";
匹配算法
由于在C标准函数中没有提供对于任意起始位置寻找匹配的方法(C++STL提供了find方法,但是$$O(n^2)$$复杂度),所以我们一般需要自己实现匹配算法。
在匹配算法中,我们将用于匹配的字符串称为模式串,被匹配的字符串称为匹配串,还是上面那个例子,用s1和s2去匹配,则s1是模式串,s2是匹配串。
暴力匹配
我们很容易能够想到暴力方法实现字符串匹配:
// s1: Match string
// s2: Pattern string
int match(const char s1[], const char s2[]) {
// Get length
int l1 = strlen(s1), l2 = strlen(s2);
// i: Start position of match string
// lmt: Max posible start position
for (int i = 0, lmt = l1 - l2; i <= lmt; ++i) {
// Match flag
bool f = true;
// Scanning pattern string
for (int j = 0; j < l2; ++j)
if (s1[i + j] != s2[j]) {
f = false;
break;
}
// Check if matched, then return position
if (f)
return i;
}
// Not found
return -1;
}
非常简单明了,就是$$O(n^2)$$的时间复杂度实在是有点不敢恭维了。
接下来我们来看看这样一个例子:
s1 = "abad";
s2 = "abacbcdhijk";
s1作为模式串,s2作为匹配串,来跑一下暴力算法:
一开始是这样的:
Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
---|---|---|---|---|---|---|---|---|---|---|---|---|
s1 | a | b | a | d | 0 | |||||||
j | ^ | |||||||||||
s2 | a | b | a | c | b | c | d | h | i | j | k | 0 |
i+j | ^ | |||||||||||
i | ^ |
我们看到此时s1[i + j]
和s2[j]
此时一样,所以j会往后走:
Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
---|---|---|---|---|---|---|---|---|---|---|---|---|
s1 | a | b | a | d | 0 | |||||||
j | ^ | |||||||||||
s2 | a | b | a | c | b | c | d | h | i | j | k | 0 |
i+j | ^ | |||||||||||
i | ^ |
接下来两步显然都能匹配,所以我们快进到第三步:
Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
---|---|---|---|---|---|---|---|---|---|---|---|---|
s1 | a | b | a | d | 0 | |||||||
j | ^ | |||||||||||
s2 | a | b | a | c | b | c | d | h | i | j | k | 0 |
i+j | ^ | |||||||||||
i | ^ |
此时发生了失配,所以根据暴力算法,我们移动i,复位j:
Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
---|---|---|---|---|---|---|---|---|---|---|---|---|
s1 | a | b | a | d | 0 | |||||||
j | ^ | |||||||||||
s2 | a | b | a | c | b | c | d | h | i | j | k | 0 |
i+j | ^ | |||||||||||
i | ^ |
但是实际上这样真的好吗?我们发现s2在从b开始时,很明显不可能匹配,因为s1的开头是a,所以更好的移动方法应该是把j移动到1,把i移动到2,因为两个起始位置的a已经可以匹配了:
Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
---|---|---|---|---|---|---|---|---|---|---|---|---|
s1 | a | b | a | d | 0 | |||||||
j | ^ | |||||||||||
s2 | a | b | a | c | b | c | d | h | i | j | k | 0 |
i+j | ^ | |||||||||||
i | ^ |
我们看见此时虽然i和j变了,但是i+j
并没有改变,而像这样子的例子其实还有很多,比如下面这个:
Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
s1 | a | b | a | b | d | 0 | |||||||
j | ^ | ||||||||||||
s2 | a | b | a | b | c | b | c | d | h | i | j | k | 0 |
i+j | ^ | ||||||||||||
i | ^ |
如果按照暴力算法来,那么下一步会变成这样:
Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
s1 | a | b | a | b | d | 0 | |||||||
j | ^ | ||||||||||||
s2 | a | b | a | b | c | b | c | d | h | i | j | k | 0 |
i+j | ^ | ||||||||||||
i | ^ |
但是更好的方法其实应该这样:
Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
s1 | a | b | a | b | d | 0 | |||||||
j | ^ | ||||||||||||
s2 | a | b | a | b | c | b | c | d | h | i | j | k | 0 |
i+j | ^ | ||||||||||||
i | ^ |
同样,还是i和j改变了,i+j
没有变。
那么这时候我们可以完全不需要i这个变量了,把i+j给定义成一个新的变量k,因为如果按照我们想出的这个跳转方法来看,k一定是递增的,那么接下来就是怎么处理j的跳转和k在什么情况下会递增了。
万幸的是,已经有前人把这种思想变成了一个著名算法——KMP。
KMP算法
KMP算法由D.E.Knuth、J.H.Morris和V.R.Pratt提出的,KMP取的就是他们名字的首字母。
在KMP算法中,核心思想是next[i]
数组。next[i]
数组定义为:在字符串s[0..i-1]
中最大的公共真前后缀长度。
这里需要说明,一个字符串的真前后缀是不包括这个字符串本身的。
用上面的一个例子:
Index | 0 | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|---|
s1 | a | b | a | b | d | 0 |
next | -1 | 0 | 0 | 1 | 2 | 0 |
由于i为0时,字符串s[0..i-1]
不存在,所以定义next[0]
为-1。
i为1时,字符串a的真前后缀都是空串,所以next[1]
为0。
i为2时,字符串ab的真前缀为∅、a,真后缀为∅、b,所以最长的公共前后缀依然是空串,所以next[2]
为0。
i为4时,字符串abab的真前缀为∅、a、ab、aba,真后缀为∅、b、ab、bab,所以最长的公共前后缀为ab,所以next[4]
为2。
那么这个数组有啥用呢?我们再把上面的例子搬下来,但这次我们把next数组一起弄上去:
Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
next | -1 | 0 | 0 | 1 | 2 | 0 | |||||||
s1 | a | b | a | b | d | 0 | |||||||
j | ^ | ||||||||||||
s2 | a | b | a | b | c | b | c | d | h | i | j | k | 0 |
k | ^ |
下一步:
Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
next | -1 | 0 | 0 | 1 | 2 | 0 | |||||||
s1 | a | b | a | b | d | 0 | |||||||
j | ^ | ||||||||||||
s2 | a | b | a | b | c | b | c | d | h | i | j | k | 0 |
k | ^ |
看!在发生失配之后,j就被赋值成了next[j]
。
所以next数组就是帮助j进行跳转的。
那么如何计算next数组呢?其实非常简单:
// const char s[]: Pattern string
// int next: Next array
void getNext(const char s[], int next[]) {
// s[0..-1] not exists, so assign next[0] to -1
next[0] = -1;
// Find next
for (int i = 0, j = -1; s[i];)
if(j == -1 || s[i] == s[j]) {
++i;
++j;
next[i] = j;
}
else
j = next[j];
}
需要注意的是,我们如果要使用next数组,一定是使用模式串的next数组。
这个代码实在是非常简单,我们来一步一步演算一下:
Index | -1 | 0 | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|---|---|
s | a | b | a | b | d | 0 | |
next | -1 | ||||||
i | ^ | ||||||
j | ^ |
一开始的状态如上,要注意的是j此时为-1,其表示next[0]
。
由于j为-1,所以下一步i和j都要向后推进,并置next[1]
为0,此时才开始正式比较:
Index | -1 | 0 | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|---|---|
s | a | b | a | b | d | 0 | |
next | -1 | 0 | |||||
i | ^ | ||||||
j | ^ |
此时i和j所指向的字符不同,让j赋值为next[j]
:
Index | -1 | 0 | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|---|---|
s | a | b | a | b | d | 0 | |
next | -1 | 0 | |||||
i | ^ | ||||||
j | ^ |
然后又是推进i和j:
Index | -1 | 0 | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|---|---|
s | a | b | a | b | d | 0 | |
next | -1 | 0 | 0 | ||||
i | ^ | ||||||
j | ^ |
接下来比较i和j指向的字符,他们相等,所以继续推进并修改next数组:
Index | -1 | 0 | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|---|---|
s | a | b | a | b | d | 0 | |
next | -1 | 0 | 0 | 1 | |||
i | ^ | ||||||
j | ^ |
i和j指向字符依然相等,继续:
Index | -1 | 0 | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|---|---|
s | a | b | a | b | d | 0 | |
next | -1 | 0 | 0 | 1 | 2 | ||
i | ^ | ||||||
j | ^ |
这里又不相等了,所以回退j为next[j]
:
Index | -1 | 0 | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|---|---|
s | a | b | a | b | d | 0 | |
next | -1 | 0 | 0 | 1 | 2 | ||
i | ^ | ||||||
j | ^ |
仍然不相等,继续回退:
Index | -1 | 0 | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|---|---|
s | a | b | a | b | d | 0 | |
next | -1 | 0 | 0 | 1 | 2 | ||
i | ^ | ||||||
j | ^ |
此时j为-1了,所以到了最后一步:
Index | -1 | 0 | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|---|---|
s | a | b | a | b | d | 0 | |
next | -1 | 0 | 0 | 1 | 2 | 0 | |
i | ^ | ||||||
j | ^ |
至此,算法模拟完毕。
经过观察不难看出,i和j其实指示的是一个可能的相同前后缀的结束位置。
我们只要指定了这两个位置,就可以同时推进i和j来检查前后缀是否相等,如果遇到了不相等的情况,那么显然这个最长的长度就是j,表明s[0..j-1]
这个前缀和s[i-j+1..i-1]
这个后缀是相等的,且长度为j。
那么当i和j失配的时候,为什么要让j等于next[j]
来跳转呢?
因为当前的前后缀可能已经不能继续扩展下去了,但是我们利用next[j]
可以找到之前已经发现的公共前缀来继续匹配,我们举一个例子:
Index | -1 | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
---|---|---|---|---|---|---|---|---|
s | a | b | a | b | a | c | 0 | |
next | -1 | 0 | 0 | 1 | 2 | 3 | ||
i | ^ | |||||||
j | ^ |
这里我们试图匹配的前缀和后缀分别是abab和abac,明显无法匹配,所以我们跳转j:
Index | -1 | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
---|---|---|---|---|---|---|---|---|
s | a | b | a | b | a | c | 0 | |
next | -1 | 0 | 0 | 1 | 2 | 3 | ||
i | ^ | |||||||
j | ^ |
而这里就变成了我们需要试图匹配的前后缀分别为ab和ac,我们之间跳过了一个a和a的匹配,因为我们通过next数组已经知道了他们是一样的,所以我们可以直接快进到ab和ac的匹配。
也就是说,这种操作其实类似于试图把一个前缀“续上”,这样子可以利用已知信息来更新最大长度。
那么知道了next数组,那么按照我们之前发现的匹配方法,就能得到如下代码:
// const char s1[]: Match string
// const char s2[]: Pattern string
// int next[]: Next array
int match(const char s1[], const char s2[], int next[]) {
for (int i = 0, j = 0; s1[i];)
if (j == -1 || s1[i] == s2[j]) {
++i;
++j;
// If matched, then return position
if (!s2[j])
return i - strlen(s2);
}
else
j = next[j];
// Not matched
return -1;
}
模拟演算就不做了,匹配函数和求next函数看起来其实很像,你甚至可以认为求next本质上就是模式串自己在和自己做匹配,即找相同前后缀。
KMP算法比暴力算法已经不知道高到哪里去了,它的时间复杂度为$$O(n+m)$$,其中n和m分别为匹配串和模式串的长度。
优化KMP
朴素的KMP已经能做到很优了,所以再怎么优化也仅仅是停留在常数上了,这就出现了KMP的一种优化写法,这种优化主要体现在next数组的不同上,我们先来看看优化的写法:
// const char s[]: Pattern string
// int next[]: Next array
void getNext(const char s[], int next[]) {
next[0] = -1;
for (int i = 0, j = -1; s[i];)
if (j == -1 || s[i] == s[j]) {
++i;
++j;
// ==== Not optimized ====
// next[i] = j
// =======================
next[i] = (s[i] == s[j] ? next[j] : j);
}
else
j = next[j];
}
我们看到,优化过后主要就是内部修改next数组的部分被换成了一个三目表达式,这个表达式等同于:
if (s[i] == s[j])
next[i] = next[j];
else
next[i] = j;
为啥这么改呢?我们来看看例子:
Index | 0 | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|---|
s | a | a | a | a | d | 0 |
next_pure | -1 | 0 | 1 | 2 | 3 | 0 |
next_optimize | -1 | -1 | -1 | -1 | -1 | 0 |
next_pure是没有优化的next数组,next_optimized是优化过的next数组,乍一看感觉多了很多-1,但是这正是关键所在,我们来用aaaad去匹配aaaac看看。
如果使用未优化的next数组,算法会这样走:
第一到四步:
Index | -1 | 0 | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|---|---|
next | -1 | 0 | 0 | 1 | 2 | 0 | |
s1 | a | a | a | a | d | 0 | |
j | ^ | ||||||
s2 | a | a | a | a | c | 0 | |
i | ^ |
Index | -1 | 0 | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|---|---|
next | -1 | 0 | 0 | 1 | 2 | 0 | |
s1 | a | a | a | a | d | 0 | |
j | ^ | ||||||
s2 | a | a | a | a | c | 0 | |
i | ^ |
Index | -1 | 0 | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|---|---|
next | -1 | 0 | 0 | 1 | 2 | 0 | |
s1 | a | a | a | a | d | 0 | |
j | ^ | ||||||
s2 | a | a | a | a | c | 0 | |
i | ^ |
Index | -1 | 0 | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|---|---|
next | -1 | 0 | 0 | 1 | 2 | 0 | |
s1 | a | a | a | a | d | 0 | |
j | ^ | ||||||
s2 | a | a | a | a | c | 0 | |
i | ^ |
我们在第五步发生了失配:
Index | -1 | 0 | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|---|---|
next | -1 | 0 | 0 | 1 | 2 | 0 | |
s1 | a | a | a | a | d | 0 | |
j | ^ | ||||||
s2 | a | a | a | a | c | 0 | |
i | ^ |
这时我们j就要回退了,接下来几步是这样的:
Index | -1 | 0 | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|---|---|
next | -1 | 0 | 0 | 1 | 2 | 0 | |
s1 | a | a | a | a | d | 0 | |
j | ^ | ||||||
s2 | a | a | a | a | c | 0 | |
i | ^ |
Index | -1 | 0 | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|---|---|
next | -1 | 0 | 0 | 1 | 2 | 0 | |
s1 | a | a | a | a | d | 0 | |
j | ^ | ||||||
s2 | a | a | a | a | c | 0 | |
i | ^ |
Index | -1 | 0 | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|---|---|
next | -1 | 0 | 0 | 1 | 2 | 0 | |
s1 | a | a | a | a | d | 0 | |
j | ^ | ||||||
s2 | a | a | a | a | c | 0 | |
i | ^ |
我们发现最后j退回到了-1,因为无论如何匹配,a前缀都无法接到c上,既然如此,那么何不把这些完全没有匹配可能的位置干脆全部置为-1,这样一步就可以到了。
所以这就是KMP的优化(常数)写法,但是需要注意的是,如果采用了这种优化写法,那么KMP算法只能用来完成字符串匹配的工作了,因为我们把next数组的意义给改变了,导致一些本来可以利用next数组性质解决的问题变得不可解。
KMP另类应用
KMP算法不仅仅可以用来字符串匹配,它还有一些另类应用,但是这些其实都是基于next数组的,也就是在以下的应用场景中,你不能使用KMP优化算法。
公共前后缀问题
有些问题需要使用公共前后缀长度,这一类问题基本上按照next数组的定义来解决就可以了,故不多赘述。
循环子串问题
next数组有一个非常特殊的性质:
假设字符串长度为len,则len-next[len]
为一个可能的最小循环长度,如果要形成循环,那么需要当且仅当len可以被len-next[len]
整除时,即len % (len - next[len] == 0
,循环成立,且最大循环数量为len / (len - next[len])
,而这个最小的循环节为s[0..len-next[len]-1]
。
我们可以简单证明一下这个式子的正确性:
假设有字符串S[0..7]
,且已知next[8]
为6,所以由next定义可知子串S[0..5]
和S[2..7]
是一样的。
计算len-next[len]
得2,且8可以被2整除,所以最小循环节应该为S[0..1]
。
又由子串S[0..5]
和S[2..7]
相同,故可以得出S[0..1]
和S[2..3]
相同,S[2..3]
和S[4..5]
相同,S[4..5]
和S[6..7]
相同,故证。
参考例题
题号 | 标签 | 相对难度 | 链接 |
---|---|---|---|
Lougu P3375 | KMP模板 | 1 | 【模板】KMP字符串匹配 |
POJ 3080 | 多字符串匹配问题 | 2 | Blue Jeans |
Luogu P4391 | 最小循环节 | 2 | [BOI2009]Radio Transmission 无线传输 |
Luogu P3435 | next数组性质利用 | 3 | [POI2006]OKR-Periods of Words |
UVA 12604 | 变种字符串匹配 | 3 | Caesar Cipher |
文档最后编辑于01月17日
评论