字符串模式匹配（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。输入样例:qwerabcabhlkabcab输出样例:-1 -1 -1 0 14#include bits/stdc.h using namespace std; const int n1e55; int nxt[n]; void getnext(string p,int next[]) { next[0]-1; int i1;//开始比较的指针 int len0;//前后缀字符相同的长度 while(ip.length()) { if(p[i]p[len])//前后缀匹配成功 { len; next[i]len-1; } else if(len0)//完全没匹配 next[i]-1; else lennext[len-1]1;//看上一个有匹配过的 } } int kmp(string p,string s,int next[]) { getnext(p,next); int i0,j0; while(is.length()) { if(s[i]p[j]) { i; j; } else if(j0) jnext[j-1]1;//不匹配回退 else i;//第一个就不匹配 if(jp.length()) return i-j; } return -1; } int main() { string s,p; cinsp; int anskmp(p,s,nxt); for(int i0;ip.length();i) coutnxt[i] ; coutendlans; return 0; }