KMP

asddddd28 · 2019-03-09 16:26:28 · 个人记录

#include<iostream>
#include<string.h>
#define MAX 1000001
using namespace std;
char str[MAX],mode_str[MAX];
int len_str,len_mode;
int next[MAX];
void init_next(){
    int i=0,j=0;
    for(i=1;i<len_mode;i++){
        while(j>0&&mode_str[i]!=mode_str[j]){
            j=next[j-1];
            j++;
        }
        if(j>=0&&mode_str[i]==mode_str[j]){
            next[i]=j;
            j++;
        }else j=0;
    }
}
void init(){
    cin>>str>>mode_str;
    len_str=strlen(str);
    len_mode=strlen(mode_str);
    for(int i=0;i<len_mode;i++) next[i]=-1;
    init_next();
}
int KMP(){
    int i=0,j=0;
    for(i=0;i<len_str;i++){
        while(j>0&&str[i]!=mode_str[j]){
            j=next[j-1];
            j++;
        }
        if(str[i]==mode_str[j])
            j++;
        if(j==len_mode){
            return i-j+2;
        }
    }
    return -1;
}
int main(){
    init();
    KMP();
    //for(int i=0;i<len_mode;i++) cout<<next[i]+1<<" ";
    return 0;
}

note

str[ ]：字符串

mode_str[ ]: 模式串

next[ ]: 最大前后缀（上一个相同位置）

*next求法：

i:1 - len_mode

j:next[i] (i的上一个相同的位置)

if（str[i]==mode[j]）//跳到下一个位置继续匹配 \   i++;
  j++;

if（str[i]!=mode）//j往前跳 \   j=next[j-1]; //上一个已匹配位置 \   j++;//上一个未匹配位置