不同于算法基础课的KMP模板

// KMP
#include<bits/stdc++.h>

using namespace std;

const int N = 1e6;
char s[N]; // 主串
char m[N]; // 字串
int ne[N];


int GetIndex(char s[],char m[])
{
    int i1 = 0,i2 = 0;

    int len1 = strlen(s);
    int len2 = strlen(m);

    while(i1 < len1 && i2 < len2)
    {
        if(s[i1] == m[i2])
        {
            i1 ++;
            i2 ++;
        }
        else if(ne[i2] == -1) // i2 == 0
            i1 ++;
        else 
            i2 = ne[i2];

    }
    // i1越界 或者 i2越界
    return i2 == len2 ? i1 - i2 : -1; // 返回第一匹配成功的初始位置。
}

void GetNextArray(char m[])
{
    int len = strlen(m);

    if(len == 1) 
    {
        ne[0] = -1;
        return;
    }

    ne[0] = -1;
    ne[1] = 0;

    int i = 2;
    int cn = 0;

    while(i < len)
    {
        if(m[i - 1] == m[cn])
            ne[i++] = ++cn;
        else if(cn > 0)
            cn = ne[cn];
        else
            ne[i++] = 0;
    }
}

int main()
{
    cin >> s >> m;

    GetNextArray(m);

    cout << GetIndex(s,m) << endl;

    return 0;
}