一对一匹配，KMP算法

from:https://www.cnblogs.com/yjiyjige/p/3263858.html

模板：

#include<iostream>
#include<string>
#include<cstring>

using namespace std;
const int N = 1e5;     //字符串最大长度
string s, t;             //s主串，t模式串
int Next[N];         //不匹配时需要移动的位置

void findNext() {
    int k = -1;
    int i = 0;
    memset(Next, -1, sizeof Next);
    while (i < t.length() - 1) {
        if (k == -1 || t[i] == t[k]) {       //有重复的字符时
            if (t[++i] == t[++k])      // 当两个字符相等时要跳过
                Next[i] = Next[k];
            else
                Next[i] = k;
        } else
            k = Next[k];
    }
}

int KMP() {
    int i = 0, j = 0;
    while (i != s.length() && j != t.length()) {
        if (j == -1 || s[i] == t[j]) {  //当j为-1时，要移动的是i，当然j也要归0
            i++;
            j++;
        } else
            j = Next[j];          //j回到指定位置
    }
    if (j == t.length())         //找到匹配的
        return i - j;
    else
        return -1;
}

int main() {
    cin >> s >> t;
    findNext();
    int tPos = KMP();
    if (tPos == -1)
        cout << "Not has t!" << endl;
    else
        cout << "t is in " << tPos << "!" << endl;
    return 0;
}

/*
Input:
bacbababadababacambabacaddababacasdsd
ababaca
Output:
t is in 10!
*/