**

KMP字符串匹配算法代码（模板）

**

#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
using namespace std;
int next[105];//字符串里面某个字符之前的字符串所拥有的最大公共前后缀长度  
 
//寻找前后缀的过程实质也是一个字符串的匹配 ，相当于2个自身进行匹配字符串 
void get_next(char* p){//生成next数组，
     int len = strlen(p);
  next[0] = -1;
  int k = -1,j = 0;
  while(j < len-1){
   if(k==-1||p[k]==p[j]){//如果模式串指针回到了起点或者找到匹配位置 
    k++;
    j++;
    next[j] = k;//存储当前的最大前后缀长度 
   }else{
    k = next[k];//不匹配，将模式串右移 
   }
  } 
}
int kmp(char* s,char* p){//过程原理和 get_next一样 
 int s_len = strlen(s);
 int p_len = strlen(p);
 int i = 0,j = 0;
 while(i < s_len&&j < p_len){
     if(j==-1||s[i]==p[j]){
      i++;
      j++;
  }else{
   j = next[j];//即将模式串右移了（j-next[j])位 
  } 
 }
 if(j >= p_len)
   return i - j;
 else
    return -1;
}
int main(){
    char str[] = "bbc abcdab abcdabd";
    char pat[] = "abcdabd";
    get_next(pat);
 cout<<"位置为："<<kmp(str,pat)<<endl;
 
 return 0;
}