【算法】字符串基础

字符串

字符串是由字符按顺序排列形成的串结构。
在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作为匹配串,来跑一下暴力算法:
一开始是这样的:

Index01234567891011
s1abad0
j^
s2abacbcdhijk0
i+j^
i^

我们看到此时s1[i + j]s2[j]此时一样,所以j会往后走:

Index01234567891011
s1abad0
j^
s2abacbcdhijk0
i+j^
i^

接下来两步显然都能匹配,所以我们快进到第三步:

Index01234567891011
s1abad0
j^
s2abacbcdhijk0
i+j^
i^

此时发生了失配,所以根据暴力算法,我们移动i,复位j:

Index01234567891011
s1abad0
j^
s2abacbcdhijk0
i+j^
i^

但是实际上这样真的好吗?我们发现s2在从b开始时,很明显不可能匹配,因为s1的开头是a,所以更好的移动方法应该是把j移动到1,把i移动到2,因为两个起始位置的a已经可以匹配了

Index01234567891011
s1abad0
j^
s2abacbcdhijk0
i+j^
i^

我们看见此时虽然i和j变了,但是i+j并没有改变,而像这样子的例子其实还有很多,比如下面这个:

Index01234567891011
s1ababd0
j^
s2ababcbcdhijk0
i+j^
i^

如果按照暴力算法来,那么下一步会变成这样:

Index01234567891011
s1ababd0
j^
s2ababcbcdhijk0
i+j^
i^

但是更好的方法其实应该这样:

Index01234567891011
s1ababd0
j^
s2ababcbcdhijk0
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]最大的公共真前后缀长度
这里需要说明,一个字符串的前后缀是不包括这个字符串本身的。
用上面的一个例子:

Index012345
s1ababd0
next-100120

由于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数组一起弄上去:

Index01234567891011
next-100120
s1ababd0
j^
s2ababcbcdhijk0
k^

下一步:

Index01234567891011
next-100120
s1ababd0
j^
s2ababcbcdhijk0
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-1012345
sababd0
next-1
i^
j^

一开始的状态如上,要注意的是j此时为-1,其表示next[0]
由于j为-1,所以下一步i和j都要向后推进,并置next[1]为0,此时才开始正式比较:

Index-1012345
sababd0
next-10
i^
j^

此时i和j所指向的字符不同,让j赋值为next[j]

Index-1012345
sababd0
next-10
i^
j^

然后又是推进i和j:

Index-1012345
sababd0
next-100
i^
j^

接下来比较i和j指向的字符,他们相等,所以继续推进并修改next数组:

Index-1012345
sababd0
next-1001
i^
j^

i和j指向字符依然相等,继续:

Index-1012345
sababd0
next-10012
i^
j^

这里又不相等了,所以回退j为next[j]

Index-1012345
sababd0
next-10012
i^
j^

仍然不相等,继续回退:

Index-1012345
sababd0
next-10012
i^
j^

此时j为-1了,所以到了最后一步:

Index-1012345
sababd0
next-100120
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-10123456
sababac0
next-100123
i^
j^

这里我们试图匹配的前缀和后缀分别是abab和abac,明显无法匹配,所以我们跳转j:

Index-10123456
sababac0
next-100123
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;

为啥这么改呢?我们来看看例子:

Index012345
saaaad0
next_pure-101230
next_optimize-1-1-1-1-10

next_pure是没有优化的next数组,next_optimized是优化过的next数组,乍一看感觉多了很多-1,但是这正是关键所在,我们来用aaaad去匹配aaaac看看。
如果使用未优化的next数组,算法会这样走:
第一到四步:

Index-1012345
next-100120
s1aaaad0
j^
s2aaaac0
i^
Index-1012345
next-100120
s1aaaad0
j^
s2aaaac0
i^
Index-1012345
next-100120
s1aaaad0
j^
s2aaaac0
i^
Index-1012345
next-100120
s1aaaad0
j^
s2aaaac0
i^

我们在第五步发生了失配:

Index-1012345
next-100120
s1aaaad0
j^
s2aaaac0
i^

这时我们j就要回退了,接下来几步是这样的:

Index-1012345
next-100120
s1aaaad0
j^
s2aaaac0
i^
Index-1012345
next-100120
s1aaaad0
j^
s2aaaac0
i^
Index-1012345
next-100120
s1aaaad0
j^
s2aaaac0
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 P3375KMP模板1【模板】KMP字符串匹配
POJ 3080多字符串匹配问题2Blue Jeans
Luogu P4391最小循环节2[BOI2009]Radio Transmission 无线传输
Luogu P3435next数组性质利用3[POI2006]OKR-Periods of Words
UVA 12604变种字符串匹配3Caesar Cipher

标签: 算法, KMP, 字符串

文档最后编辑于01月17日

评论

让我也说点啥