Leetcode记录：KMP算法

7 Aug 2024

找出字符串中第一个匹配的下标

Leetcode 28. 给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。

这道题可以暴力枚举：

int strStr(string haystack, string needle) {
    int hLen = haystack.length();
    int nLen = needle.length();
    if(hLen < nLen)
        return -1;
    int start = 0;
    for(int start = 0; start < hLen - nLen + 1; ++start){
        if(haystack[start] == needle[0]){
            for(int i = 0; i < nLen; ++i){
                if(haystack[i+start] != needle[i])
                    break;
                if(i==nLen-1 && haystack[i+start] == needle[i])
                    return start;
            }
        }
    }
    return -1;
}

但是复杂度为$O(mn),m=hLen,n=nLen$.

KMP算法

KMP的经典思想就是:当出现字符串不匹配时，可以记录一部分之前已经匹配的文本内容，利用这些信息避免从头再去做匹配。 所以如何记录已经匹配的文本内容，是KMP的重点，也是后续要讲的next数组肩负的重任。 next数组就是一个前缀表（prefix table）。前缀表是用来回退的，它记录了模式串与主串(文本串)不匹配的时候，模式串应该从哪里开始重新匹配。

前缀表

为了清楚地了解前缀表的来历，我们来举一个例子：要在文本串：aabaabaafa 中查找是否出现过一个模式串：aabaaf。

可以看出，文本串中第六个字符b和模式串的第六个字符f不匹配了。如果暴力匹配，发现不匹配，此时就要从头匹配了。但如果使用前缀表，就不会从头匹配，而是从上次已经匹配的内容开始匹配，找到了模式串中第三个字符b继续开始匹配。此时就要问了前缀表是如何记录的呢？首先要知道前缀表的任务是当前位置匹配失败，找到之前已经匹配上的位置，再重新匹配，此也意味着在某个字符失配时，前缀表会告诉你下一步匹配中，模式串应该跳到哪个位置。

那么什么是前缀表：记录下标i之前（包括i）的字符串中，有多大长度的相同前缀后缀。 其中，字符串的前缀是指不包含最后一个字符的所有以第一个字符开头的连续子串。后缀是指不包含第一个字符的所有以最后一个字符结尾的连续子串。对于字符串”abcab”，它有”a” “ab” “abc” “abca” 这样四个前缀，有”b” “ab” “cab” “bcab” 这样四个后缀。

回顾一下，刚刚匹配的过程在下标5的地方遇到不匹配，模式串是指向f，然后就找到了下标2，指向b，继续匹配：如图：

下标5之前这部分的字符串（也就是字符串aabaa）的最长相等的前缀和后缀字符串是子字符串aa ，因为找到了最长相等的前缀和后缀，匹配失败的位置是后缀子串的后面，那么我们找到与其相同的前缀的后面重新匹配就可以了。所以前缀表具有告诉我们当前位置匹配失败，跳到之前已经匹配过的地方的能力。

如何计算前缀表

接下来就要说一说怎么计算前缀表。

长度为前1个字符的子串a，最长相同前后缀的长度为0。（注意字符串的前缀是指不包含最后一个字符的所有以第一个字符开头的连续子串；后缀是指不包含第一个字符的所有以最后一个字符结尾的连续子串。）
长度为前2个字符的子串aa，最长相同前后缀的长度为1。
长度为前3个字符的子串aab，最长相同前后缀的长度为0。
以此类推：长度为前4个字符的子串aaba，最长相同前后缀的长度为1。长度为前5个字符的子串aabaa，最长相同前后缀的长度为2。长度为前6个字符的子串aabaaf，最长相同前后缀的长度为0。

那么把求得的最长相同前后缀的长度就是对应前缀表的元素，如图：

可以看出模式串与前缀表对应位置的数字表示的就是：下标i之前（包括i）的字符串中，有多大长度的相同前缀后缀。再来看一下如何利用前缀表找到当字符不匹配的时候应该指针应该移动的位置。如动画所示：

找到的不匹配的位置，那么此时我们要看它的前一个字符的前缀表的数值是多少。前一个字符的前缀表的数值是2，所以把下标移动到下标2的位置继续比配。最后就在文本串中找到了和模式串匹配的子串了。

前缀表与next数组

很多KMP算法的实现都是使用next数组来做回退操作，那么next数组与前缀表有什么关系呢？next数组就可以是前缀表，但是很多实现都是把前缀表统一减一（右移一位，初始位置为-1）之后作为next数组。

其实这并不涉及到KMP的原理，而是具体实现，next数组既可以就是前缀表，也可以是前缀表统一减一（右移一位，初始位置为-1）。

使用next数组来匹配

以下我们以前缀表统一减一之后的next数组来做演示。有了next数组，就可以根据next数组来匹配文本串s，和模式串t了。注意next数组是新前缀表（旧前缀表统一减一了）。

匹配过程动画如下：

构造next数组

next[i] 等于满足下述要求的 x 的最大值：s[0:i] 具有长度为 x+1 的完全相同的前缀和后缀。 构造next数组其实就是计算模式串s，前缀表的过程。主要有如下三步：

初始化定义两个指针i和j，j指向前缀末尾位置，i指向后缀末尾位置。然后还要对next数组进行初始化赋值：
```
 int j = -1;
 next[0] = j;
```
处理前后缀不相同的情况如果 s[i] 与 s[j+1] 不相同，也就是遇到前后缀末尾不相同的情况，就要向前回退，找s.substr(0,i)更小长度的相同前后缀。因为 s.substr(0,j+1) == substr(i-j-1,j+1)， s.substr(0,next[j]+1) = s.substr(j-next[j],next[j]+1) =s.substr(i-next[j]-1,next[j]+1) 所以，s[i] 与 s[j+1] 不相同，就要找 j+1前一个元素在next数组里的值（就是next[j]）。
处理前后缀相同的情况如果 s[i] 与 s[j + 1] 相同，那么就同时向后移动i 和j 说明找到了相同的前后缀，同时还要将j（前缀的长度）赋给next[i], 因为next[i]要记录相同前后缀的长度。

总体程序如下:

void getNext(int* next, const string& s){
    int j = -1;
    next[0] = j;
    for(int i = 1; i < s.size(); i++) { // 注意i从1开始
        while (j >= 0 && s[i] != s[j + 1]) { // 前后缀不相同了
            j = next[j]; // 向前回退
        }
        if (s[i] == s[j + 1]) { // 找到相同的前后缀
            j++;
        }
        next[i] = j; // 将j（前缀的长度）赋给next[i]
    }
}

使用next数组来做匹配

int j = -1; // 因为next数组里记录的起始位置为-1
for (int i = 0; i < s.size(); i++) { // 注意i就从0开始
    while(j >= 0 && s[i] != t[j + 1]) { // 不匹配
        j = next[j]; // j 寻找之前匹配的位置
    }
    if (s[i] == t[j + 1]) { // 匹配，j和i同时向后移动
        j++; // i的增加在for循环里
    }
    // j 从 -1 开始，所以最后是t.size()-1.
    if (j == (t.size() - 1) ) { // 文本串s里出现了模式串t
        return (i - t.size() + 1);
    }
}

总体代码如下：

void getNext(int* next, const string& s) {
    int j = -1;
    next[0] = j;
    for(int i = 1; i < s.size(); i++) { // 注意i从1开始
        while (j >= 0 && s[i] != s[j + 1]) { // 前后缀不相同了
            j = next[j]; // 向前回退
        }
        if (s[i] == s[j + 1]) { // 找到相同的前后缀
            j++;
        }
        next[i] = j; // 将j（前缀的长度）赋给next[i]
    }
}
int strStr(string haystack, string needle) {
    if (needle.size() == 0) {
        return 0;
    }
    vector<int> next(needle.size());
    getNext(&next[0], needle);
    int j = -1; // // 因为next数组里记录的起始位置为-1
    for (int i = 0; i < haystack.size(); i++) { // 注意i就从0开始
        while(j >= 0 && haystack[i] != needle[j + 1]) { // 不匹配
            j = next[j]; // j 寻找之前匹配的位置
        }
        if (haystack[i] == needle[j + 1]) { // 匹配，j和i同时向后移动
            j++; // i的增加在for循环里
        }
        if (j == (needle.size() - 1) ) { // 文本串s里出现了模式串t
            return (i - needle.size() + 1);
        }
    }
    return -1;
}

重复的子字符串

Leetcode 459. 给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。

除了暴力枚举之外还有一种方法：我们将两个 s 连在一起，并移除第一个和最后一个字符。如果 s 是该字符串的子串，那么 s 就满足题目要求。

证明： 如果长度为 $n$ 的字符串 s 是字符串 t=s+s 的子串，并且 s 在 t 中的起始位置不为 $0$ 或 $n$，那么 s 就满足题目的要求。证明过程如下：

我们设 s 在 t 中的起始位置为 $i\in(0,n)$。也就是说，t 中从位置 $i$ 开始的 $n$ 个连续的字符，恰好就是字符串s。那么我们有：

\[s[0:n−1]=t[i:n+i−1].\]

由于 t 是由两个 s 拼接而成的，我们可以将 $t[i:n+i−1]$ 分成位置 $n−1$ 左侧和右侧两部分：

\[s[0:n−i−1]=t[i:n−1],\] \[s[n−i:n−1]=t[n:n+i−1]=t[0:i−1]\]

每一部分都可以对应回 s：

\[s[0:n−i−1]=s[i:n−1],\] \[s[n−i:n−1]=s[0:i−1]\]

这说明，s 是一个 可旋转 的字符串：将 s 的前 $i$ 个字符保持顺序，移动到 s 的末尾，得到的新字符串与 s 相同。也就是说，在模 $n$ 的意义下，$s[j]=s[j+i]$ 对于任意的 $j$ 恒成立。如果我们不断地连写这个等式：

$s[j]=s[j+i]=s[j+2i]=s[j+3i]=\ldots$ 那么所有满足 $j_0 =j+ki$ 的位置 $j_0$ 都有 $s[j]=s[j_0]$，$j$ 和 $j_0$ 在模 $i$ 的意义下等价。由于我们已经在模 $n$ 的意义下讨论这个问题，因此 $j$ 和 $j_0$ 在模 $gcd(n,i)$ 的意义下等价，其中 gcd 表示最大公约数。也就是说，字符串 s 中的两个位置如果在模 $gcd(n,i)$ 的意义下等价，那么它们对应的字符必然是相同的。

由于 $gcd(n,i)$ 一定是 $n$ 的约数，那么字符串 s 一定可以由其长度为 $gcd(n,i)$ 的前缀重复构成。

bool repeatedSubstringPattern(string s) {
        return (s + s).find(s, 1) != s.size();
    }

我们也可以采用KMP算法来替换库函数:

bool kmp(const string& query, const string& pattern) {
        int n = query.size();
        int m = pattern.size();
        vector<int> fail(m, -1);
        for (int i = 1; i < m; ++i) {
            int j = fail[i - 1];
            while (j != -1 && pattern[j + 1] != pattern[i]) {
                j = fail[j];
            }
            if (pattern[j + 1] == pattern[i]) {
                fail[i] = j + 1;
            }
        }
        int match = -1;
        for (int i = 1; i < n - 1; ++i) {
            while (match != -1 && pattern[match + 1] != query[i]) {
                match = fail[match];
            }
            if (pattern[match + 1] == query[i]) {
                ++match;
                if (match == m - 1) {
                    return true;
                }
            }
        }
        return false;
    }

    bool repeatedSubstringPattern(string s) {
        return kmp(s + s, s);
    }

在正确性证明部分，如果我们设 $i$ 为最小的起始位置，那么一定有 $gcd(n,i)=i$，即 $n$ 是 $i$ 的倍数。这说明字符串 s 是由长度为 $i$ 的前缀重复构成；

由于 fail[n−1] 表示 s 具有长度为fail[n−1]+1的完全相同的（且最长的）前缀和后缀。那么对于满足题目要求的字符串，一定有 fail[n−1]=n−i−1，即 i=n−fail[n−1]−1；对于不满足题目要求的字符串，$n$ 一定不是 n−fail[n−1]−1 的倍数。上述所有的结论都可以很容易地使用反证法证出。因此，我们在预处理出 fail 数组后，只需要判断 $n$ 是否为 n−fail[n−1]−1 的倍数即可。

更直观的图如下：

也就是说只要最长相等前后缀有重叠，并且总长度是后缀不包含的子串长度的倍数，就满足题目要求。

void getNext (int* next, const string& s){
    next[0] = -1;
    int j = -1;
    for(int i = 1;i < s.size(); i++){
        while(j >= 0 && s[i] != s[j + 1]) {
            j = next[j];
        }
        if(s[i] == s[j + 1]) {
            j++;
        }
        next[i] = j;
    }
}
bool repeatedSubstringPattern (string s) {
    if (s.size() == 0) {
        return false;
    }
    int next[s.size()];
    getNext(next, s);
    int len = s.size();
    if (next[len - 1] != -1 && len % (len - (next[len - 1] + 1)) == 0) {
        return true;
    }
    return false;
}

数据结构与算法