字符串模式匹配（KMP）

题目描述:
给定主串 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; }