KMP算法

KMP算法介绍

　　KMP算法是一种用于在一个源字符串 $S$ 中找目标字符串 $T$ 的所在位置的算法。相较于暴力匹配，它通过对目标字符串 $T$ 的结构进行分析，预先处理得到一些数据，从而能够在匹配过程中跳过大多无用的匹配操作，从而提高查找效率。
　　在暴力匹配中，目标字符串与源字符串相应位置匹配不上时，会将匹配的位置后移一位。比如在源字符串 $abcde$ 中试图找到 $cde$ 的位置，会先试图将 $S$ 中的 $abc$ 与 $cde$ 进行匹配。匹配失败后会将对齐的位置往后移动，变为 $bcd$ 来与 $cde$ 进行匹配。在源字符串和目标字符串都比较长时这种慢慢移动然后不断匹配的方法就会比较慢。因此KMP算法让它在匹配失败后不止移动一位，而是尽量多移动一些（具体移动多少取决于从目标串提取出的一些数据），从而提升一些效率。

KMP算法的匹配位置移动原则

　　为了提升效率，匹配失败后自然是希望尽可能地多往后移动一些，从而多减少一些无用的匹配行为，也就是“不可能匹配成功”的匹配行为。但是也不能想当然地移动，不然可能错失能够正确匹配的位置。KMP算法中，给出的合适的移动距离与本次匹配时成功匹配的部分的最长公共前后缀长度有关。
　　让我们看以下的例子：
$$
\begin{cases}
S = abxabxaby\\
T = abxaby
\end{cases}
$$
　　当KMP算法试图在 $S$ 中寻找 $T$ 的所在位置时，会先将 $S$ 的 $abxabx$ 与 $abxaby$ 进行匹配：
$$
\begin{aligned}
&S: &abxabx\quad&aby\\
&T: &abxaby\quad&
\end{aligned}
$$
　　那么可以成功匹配的部分有 $abxab$ 。由于这个是匹配成功的部分，那么它自然会同时存在于$S$和$T$当中。不难观察到，$abxab$具有一个长度为$2$的公共前后缀 $ab$ ，于是KMP算法会将 $T$ 的位置进行适当地移动，让 $T$ 的前缀部分对齐到 $S$ 中相应的后缀部分：
$$
\begin{aligned}
&S:\quad abx &abxaby\\
&T:\quad &abxaby
\end{aligned}
$$
　　然后KMP算法会不断重复这个过程，直到整个 $T$ 都匹配成功(如果有需要，也可以让它继续匹配下去寻找多个所在位置)，或者移动到末尾仍然无法匹配。

KMP算法的核心

　　通过上面的例子不难看出，KMP算法它效率比较高的原因就是因为它通过匹配成功的部分的字符串的公共前后缀长度来得出它可以放心后移的距离，这个距离或许不一定是最大的，但是也足够用。如果你对 “为什么这样移动不会错过正确的位置” 感到疑惑，那么可以观察以下例子：
　　假设有源字符串 $S$ 和 $T$ ，其中 $x$ 不是指代字符’$x$’，只是为了体现长度而占位：
$$
\begin{cases}
S = xxxxxxxxx\\
T = xxxxxx
\end{cases}
$$
　　假设第一次匹配中，匹配成功的部分长度是 $5$ (假设1) ，并且其最长公共前后缀是 $2$ (假设2)，那么根据KMP算法，它会对齐到以下状态：
$$
\begin{aligned}
&S:\quad xxx \quad&xxxxxx\\
&T: \quad&xxxxxx
\end{aligned}
$$
　　同时，假设我们并不将 $T$ 往后移动 $3$ 位，而是只移动 $2$ 位，并且能够匹配成功整个 $T$ (假设3)：
$$
\begin{aligned}
&S:\quad xx \quad&xxxxxx&\quad x\\
&T: \quad&xxxxxx&
\end{aligned}
$$
　　那么，我们现在有以下信息(下标从 $1$ 开始表示)：
$$
\begin{aligned}
1.\quad S[1\sim 5] = T[1\sim 5] \quad (假设1)\\
2.\quad S[3\sim 8] = T[1\sim 6] \quad (假设3)
\end{aligned}
$$
　　可以得到：
$$
T[1\sim 3] = S[3\sim 5] = T[3\sim 5]
$$
　　于是， $T[1\sim 5]$ 存在一个长度为 $3$ 的公共前后缀，与假设 $2$ 矛盾(当然，这里取具体的数值是为了更直观一点，如果要严谨一点的证明应该使用一个变量来表示)。因此KMP算法的移动方式不会存在 “错过了正确位置” 的情况。
　　这个最长公共前后缀不是在匹配过程中得到匹配部分的串之后才去计算的，而是在匹配之前就先对目标串进行预处理，得到它的所有前缀相应的最长公共前后缀长度，毕竟能够匹配成功的部分一定是目标串的前缀。当然，本文中的最长公共前后缀不能包括串本身，不然所有串的最长公共前后缀都是它本身了。

快速求解一个字符串的所有前缀的最长公共前后缀长度

　　假设我们已经知道了一个字符串 $T[1\sim n]$ 的所有前缀的最长公共前后缀长度，但是我们要得到的数据不止如此，它后面还有其他的字符。那么我们把后面的一个字符加入进来，设新字符串为 $T[1\sim n+1]$ (第 $n+1$ 个字符就是新加进来的字符)，现在我们可以通过已有的数据快速计算出 $T[1\sim n+1]$ 的最长公共前后缀长度。
　　上面内容提到，我们已经知道了字符串 $T[1\sim n]$ 的所有前缀的最长公共前后缀长度，现在我们假定字符串 $T[1\sim n+1]$ 的最长公共前后缀长度为 $x$ ，然后现在加入了第 $n+1$ 个字符，如果这个字符和 $T[1\sim n+1]$ 的第 $x+1$ 个字符相同，那么 $T[1\sim n+1]$ 的最长公共前后缀就是 $x+1$ 。比如 $abcxabc$ ，最长公共前后缀是 $abc$ ，现在加入了一个字符 $x$ ，而它也恰好出现在前缀 $abc$ 的后面，那么最长公共前后缀的长度就增加了$1$ ，变成了 $abcx$ 。这种情况是很好判断的，也很容易理解。
　　最关键的是，如果这第 $n+1$ 个字符和第 $x+1$ 个字符并不相同，又该如何呢？我们观察这样一个字符串: $ababxabab$ ，它的最长公共前后缀是 $abab$ ，现在新加入一个字符 $a$ ，我们根据上面的内容发现它和第 $5$ 个位置的 $x$ 不一致，那么只能退而求其次，看看次长公共前后缀。对于字符串 $ababxabab$ ，它最长公共前后缀是 $abab$ ，它的次长公共前后缀是 $ab$ ，然后不难发现，加入新的字符 $a$ 之后它和第 $3$ 个位置的 $a$ 是一致的，所以新加入的字符 $a$ 虽然破坏了之前的最长公共前后缀，但是次长公共前后缀没有被破坏，长度加了 $1$ ，于是它晋升为了最长公共前后缀 ，字符串 $T[1\sim n+1]$ 的最长公共前后缀就是 $aba$ 。如果次长还是接不上这个字符呢？那就看次次长，直到没有公共前后缀了为止（这种情况，$T[1\sim n+1]$ 的最长公共前后缀就要变为空了）。
　　那么现在还有一个问题，我们之前有的数据是字符串 $T[1\sim n]$ 的所有前缀的最长公共前后缀长度，我们怎么知道次长公共前后缀的长度呢？观察刚才的字符串 $ababxabab$ ，最长是 $abab$ ，次长是 $ab$ 。而 $ab$ 又是 $abab$ 的最长公共前后缀。这不是巧合，而是特性，一个字符串的最长公共前后缀的最长公共前后缀就是次长公共前后缀。为什么呢？ $ababxabab$ 的最长公共前后缀是 $abab$ ，也就意味着它既出现在了开头位置，也出现在了末尾位置。如果要找一个次长的公共前后缀，那么一定也是出现在开头和末尾，也就是要找一个尽可能长的字符串，能够作为开头的 $abab$ 的前缀，又能够作为末尾的 $abab$ 的后缀，而又不能是串 $abab$ 本身。那这不就是要找 $abab$ 的最长公共前后缀吗！然后又因为我们早就知道了字符串 $T[1\sim n]$ 的所有前缀的最长公共前后缀长度， $abab$ 作为 $ababxabab$ 的一个前缀，我们早就知晓它的最长公共前后缀，直接取就可以了。
　　就这样，我们可以通过从1个字符开始，不断加入新的字符，不断得到这个越来越长的字符串的所有前缀的最长公共前后缀，直到整个目标串所有字符都被处理。然后就可以根据处理出来的这些数据在KMP算法中加速目标串的后移。

代码示例（C++）

　　现在有这样一个需求，通过控制台读入两个字符串，要找出第二个字符串在第一个字符串中出现的位置的首字母所在下标列表。比如在“abcabc”中找“abc”就会找到[0, 3]。

#include <iostream>
#include <string>
#include <vector>
using namespace std;

// 计算字符串的所有前缀的最长公共前后缀长度，返回的数组中下标index表示的是前缀[0, index]对应的最长公共前后缀
vector<int> CalculateCommon(string &str){
    vector<int> ret(str.size());
    if(str.empty()){
        return ret;
    }
    ret[0] = 0;
    for(int i = 1; i < str.size(); ++i){
        /*
            假设已处理的字符串：
            "abcab" 加入新字符 'c'  
            "abcab" 最长公共前后缀 "ab"，长度2，那么应该要将str[2]（对应的中间的'c'）和新加入的字符比较
            因此总是拿已处理的字符串最长公共前缀长度作为初始比较下标
        */
        int compareIndex = ret[i-1];
        /*
            当跳出循环时，compareIndex要么是新的最长公共前后缀的前缀末尾下标，要么是-1，表示不存在公共前后缀
        */
        while(true){
            if(str[i] == str[compareIndex]){
                break;
            }
            if(compareIndex == 0){
                compareIndex--;
                break;
            }
            compareIndex = ret[compareIndex-1]; //找次长公共前后缀 
        }
        ret[i] = compareIndex + 1;
    }
    return ret;
}

// 从源字符串中找到目标字符串出现的所有位置
vector<int> FindPosition(string &src, string &target){
    vector<int> ret;
    //计算所有前缀的最长公共前后缀
    vector<int> commonLength = CalculateCommon(target);
    // offset 用于表示在匹配过程中目标串相对源串的位置偏移
    /*
        abcabc
          cab  此时偏移量为2，匹配成功
    */
    int offset = 0;
    while(offset + target.size() <= src.size()){
        //在当前偏移量情况下能否匹配成功
        int i = 0;
        while(i<target.size() && target[i] == src[offset + i]){
            ++i;
        }
        if(i == target.size()){
            ret.push_back(offset); //匹配成功
        }
        //能够匹配的字符有 i 个，考虑应该偏移多少？
        /*
            情况1：（能够匹配一些字符）
                [abcab]XXXXXX
                [abcab]Y    公共的length=2，应该偏移3，也就是 i - length
            =>  变为
                abc[ab]XXXXXX
                   [ab]cabY
            情况2：（一点都匹配不上）
                abcde
                fg         公共的length=0，此时的 i=0，似乎是偏移2，也就是target的长度？
            =>  变为
                abcde
                  fg
            情况3：
                abcdxabc
                cdx        和情况2类似，但是如果偏移3的话就会错过正确位置，偏移2应该是刚好，但是我觉得应该偏移1才通用（例如不是cdx而是bc，就只能偏移1）
            
            那么总结一下，对于有公共长度的就偏移 i - length，否则偏移1

        */
        if(i == 0){
            offset += 1;
        }else{
            offset += i - commonLength[i-1];
        }
    }
    return ret;
}

int main()
{
    string src, target;
    cin >> src >> target;
    vector<int> indexes = FindPosition(src, target);
    for(auto &index: indexes){
        cout<<"index: "<<index<<'\n';
    }
    return 0;
}

实战测试（交OJ题）

　　牛客——子串(NC13253)，将上方代码稍作修改，再加上一点其他的内容就能够通过这道题。

#include <bits/stdc++.h>
using namespace std;
const char digital[16] = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
                          'A', 'B', 'C', 'D', 'E', 'F'};

char finalStr[50005 * 64];
int strLength = 0;

// 将一个整数转换为K进制数后贴到finalStr有效字符串的末尾
void NumToKBase(int val, int k){
    char buffer[65] = {0};
    int index = 0;
    if(val == 0){
        buffer[index] = '0';
        index += 1;
    }
    while(val > 0){
        buffer[index] = digital[val % k];
        val /= k;
        index += 1;
    }
    while(index){
        index -= 1;
        finalStr[strLength] = buffer[index];
        strLength += 1;
    }
    finalStr[strLength] = '\0';
}

// 计算字符串的所有前缀的最长公共前后缀长度，返回的数组中下标index表示的是前缀[0, index]对应的最长公共前后缀
vector<int> CalculateCommon(string &str){
    vector<int> ret(str.size());
    if(str.empty()){
        return ret;
    }
    ret[0] = 0;
    for(int i = 1; i < str.size(); ++i){
        int compareIndex = ret[i-1];
        while(true){
            if(str[i] == str[compareIndex]){
                break;
            }
            if(compareIndex == 0){
                compareIndex--;
                break;
            }
            compareIndex = ret[compareIndex-1]; //找次长公共前后缀 
        }
        ret[i] = compareIndex + 1;
    }
    return ret;
}

// 判断是否能找到存在的位置
bool FindPosition(string &src, string &target){
    vector<int> ret;
    vector<int> commonLength = CalculateCommon(target);
    int offset = 0;
    while(offset + target.size() <= src.size()){
        int i = 0;
        while(i<target.size() && target[i] == src[offset + i]){
            ++i;
        }
        if(i == target.size()){
            return true; //匹配成功
        }
        if(i == 0){
            offset += 1;
        }else{
            offset += i - commonLength[i-1];
        }
    }
    return false;
}

int main(){
    int n;
    string target;
    cin >> n >> target;
    bool exist = false;
    for(int k = 2; k<= 16; ++k){
        strLength = 0;
        for(int i = 1;i<=n; ++i){
            NumToKBase(i, k);
        }
        string str = string(finalStr);
        if(FindPosition(str, target)){
            exist = true;
            break;
        }
    }
    if(exist){
        cout<<"yes\n";
    }else{
        cout<<"no\n";
    }
}