KMP算法

#include <iostream>
#include <string>
using namespace std;
const int maxn = 1e5+5;
int Next[maxn];
void GetNext(const string &p){
    int p_len = p.size();
    int i = 0;
    int j = -1;
    Next[i] = -1;
    while(i < p_len){
        if(j == -1 || p[i] == p[j]){
            i++;
            j++;
            if(p[i] != p[j])    Next[i] = j;
            else    Next[i] = Next[j];
        }
        else    j = Next[j];
    }
    return;
}
int KMP(const string &s, const string &p){
    GetNext(p);
    int i = 0;
    int j = 0;
    int s_len = s.size();
    int p_len = p.size();
    while(i < s_len && j < p_len){
        if(j == -1 || s[i] == p[j]){
            i++;
            j++;
        }
        else    j = Next[j];
    }
    if(j == p_len)    return i - j;
    else    return -1;
}