题目描述:
给定主串 s 和模式串 p，编写程序输出 p 在 s 中出现的首位置，若 p 不在 s 中则输出−1。字符串下标从0开始。

输入格式:
输入为2行，第1行主串 s，第2行为模式串 p。主串和模式串长度不超过100000。

输出格式:
输出为2行，第1行为若干整数，表示模式串 p 的失败函数值（next数组），每个整数后一个空格；第2行为一个整数，表示 p 在 s 中出现的首位置，若 p 不在 s 中则输出−1。

输入样例:
qwerabcabhlk
abcab

输出样例:
-1 -1 -1 0 1
4

#include <bits/stdc++.h>

using namespace std;

const int n=1e5+5;
int nxt[n];

void getnext(string p,int next[])
{
    next[0]=-1;
    int i=1;//开始比较的指针
    int len=0;//前后缀字符相同的长度
    while(i<p.length())
    {
        if(p[i]==p[len])//前后缀匹配成功
        {
            len++;
            next[i++]=len-1;
        }
        else if(len==0)//完全没匹配
            next[i++]=-1;
        else len=next[len-1]+1;//看上一个，有匹配过的
    }
}

int kmp(string p,string s,int next[])
{
    getnext(p,next);
    int i=0,j=0;
    while(i<s.length())
    {
        if(s[i]==p[j])
        {
            i++;
            j++;
        }
        else if(j>0) j=next[j-1]+1;//不匹配，回退
        else i++;//第一个就不匹配

        if(j==p.length()) return i-j;
    }
    return -1;
}

int main()
{
    string s,p;
    cin>>s>>p;
    int ans=kmp(p,s,nxt);
    for(int i=0;i<p.length();i++) cout<<nxt[i]<<" ";
    cout<<endl<<ans;
    return 0;
}