c++字符串匹配之kmp_c++字符串 匹配 kmp

算法转载于：Knuth,Morris and Pratt

写在前面：字符串匹配是要在主串里找模式串
字符串匹配啊，在kmp之前，你会先想到什么？
蛮力啊！！（一听就是超时の典型）
很好，复杂度呢？$O(n\times m)$。不用说滴。燃鹅如果是随机的数据。它也会接近线性。假设范围是ascii和扩展，那么每一次匹配的第一次比较只有$\frac{1}{256}$的概率通过。。。
燃鹅大部分情景不是随机的啊！！
哈哈！蛮力算法再见吧！！
<( ￣^￣)(θ(θ☆( >_<⭐

（以下场景纯属虚构，完全没有黑三位大神的意思）
正当你踌躇之时，你面前走来了三位嘉宾：
Knuth,Morris,Pratt
它们笑嘻嘻滴，可是把他们给开心坏了
他给你了一些指点：

对于蛮力算法来说，他没有利用以往的结果。以前算的，如果不匹配的话，就扔掉了。。。
为何不把tamen利用起来？
假设我们在i（对于模式串）位置跌倒，不匹配了，那么我们要找一个位置k（还是对于模式串）来再做比较。
为了保证正确性，需要满足：（p是模式串（pattern））$$p[:k]=p[(i-k):i]$$(这个使用到了python的切片）
额，会不会有一丁点抽象呢？
在k前面这一段（前缀），剪下来，名之为c
在i前面这一段，也给剪下来，然后取一个后缀，使得这个后缀长度与c相同，名之为b
应满足b=c
图呢？

对于一个i，有他对应的k，我们把它记录在一个表上，叫他next吧
燃鹅，我们没有构造方法啊
然后他们跟你说：你可以试用那个表的构造方法啊
然后你就试用了这个构造方法，做出来一段代码：

vector<int> kmp(string a, string b) {
    int n = a.size();
    int m = b.size();
    int* next = new int[m + 1];//God array
#pragma region BuildNext
//bulabulabulabulabulabulabulabulabula……
#pragma endregion
    int i = 0, j = 0;
    vector<int> ans;
    while (true) {
        //int ni = i;
        if (j == m) {
            ans.push_back(i - j);//i-j is the matched position.
            //ni = i - j + 1;//next position.
            j = next[j];
        }
        if (i == n)break;
        //i = ni;
        if (j < 0/*Guard*/ || a[i] == b[j]) {
            ++i, ++j;
        }
        else {
            j = next[j];
        }
    }
    delete[]next;
    return ans;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

关于那个哨兵guard，
是当k（上文的，不是代码的）=-1的时候，也就是直接拿-1来比对，其实是直接过掉这个位置。
如果还有不懂得话，我这里有不少哨兵，且听下面分解。。

光阴似箭，30天过去了，TRIAL EXPIRE!!啊哈哈233试用期到了
~%?…,# *'☆&℃$︿★?
≡(▔﹏▔)≡
Pia!(ｏ ‵-′)ノ”(ノ﹏<。)
(╯‵□′)╯炸弹！•••*～●
天不和尔意也，尔能咋地？
好吧，只能自己造一个next表了
思考中