kmp算法c++代码实现（完整版详解）

难理解的还是前后缀表的问题，这个表存的这些数字的目的是
就是要碰到不匹配的时候向右移位的个数
从而防止一些不必要的查找。
具体这个表里储存的什么内容呢请看下图
因为字符串下标从0开始，所以为了方便操作，我把数组整体往后移了一位
整体后移以后，我没有去掉最后最长的前后缀那个一数（因为方便我找出所有的字符串）
把最开头补上-1
为什么第一个位置是-1，是因为当他为0的时候在kmp中 当len=0时，（len=prefix[len]）之后len=-1，再加1正好是0的下标。

再看这一张图（当匹配失败时的操作）当匹配失败，查询prefix表中当前的值并将它付给len （代码中&&&&&&&&&标记位置）
这样子做的目的显而易见，我们可以少进行两次比较从而减少时间复杂度

再看这一张图，这就是为什么不删掉最长的原因，因为prefix[len] (当len=他的实际长度时)就发挥作用了 （这里对应着我代码里标*******的位置）
当找到一个时，我们可以直接移动，从而少查找了 ABA 三位
当然如果只找第一次出现的位置可以不需要储存最长的那一段表的数字也就是（ABABCDABA）

代码

#pragma GCC optimize(3,"Ofast","inline")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <math.h>
#include <string>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <stdlib.h>
#define maxn  1000005
//#define true false
//#define false true
const int MaxN = 0x3f3f3f3f;
const int MinN = 0xc0c0c00c;
const double pi = acos(-1);
typedef long long ll;
const int mod = 1e9 + 7;
using namespace std;
string s, t;
int prefix[1000];
int firstplace;
void prefix_table() {  //求前后缀表
    prefix[0] = -1;
    int i = 0, len = -1;
    while (i < s.size()) {
        if (len == -1 || s[i] == s[len]) {
            i++, len++;
            prefix[i] = len;
        }
        else  len = prefix[len];  //&&&&&&&&&&&&
    }
}

int ans_kmp() {
    int i = 0, len = 0;
    bool flag = false;
    int ans = 0;
    prefix_table();
    while (i < t.size()) {
        if (len == -1 || s[len] == t[i])  i++, len++;
        else  len = prefix[len];
        if (len == s.size()) {
            if (flag == false)  firstplace = i - s.size() + 1;
            ans++;
            cout << i - s.size() + 1 << endl;
            len = prefix[len];  //这一块处理看上图  ********
            flag = true;
        }
    }
    if (flag)  return ans;
    else  return-1;
}

int main()
{
    cin >> t;
    cin >> s;
    int sum = ans_kmp();
    cout << endl;
    if (sum) {
        cout << "出现的总次数为： " << sum << endl;
        cout << "第一次出现此字符串的位置为： " << firstplace << endl;
    }
    else   cout << "not found!" << endl;

    return 0;
}

因为也是新手，刚接触这个算法，所以有什么问题和不足欢迎大家指出。