[template] KMP string matching

KMP String matching next Array method

char* strstr(char*str,char*pattern);// The string is very small O(m.n) 

There are small strings that can be matched from end to end in the substring , The pointer doesn't have to go back to the beginning every time .
Before matching , Analyze the pattern string in detail , Make clear next The meaning of value ,
p[0 ~ j]==p[ (i-j) ~i] , From p[0] Start length is len=j+1, There are p[j]=
p[i] So once p[i+1] And t[?] It's not equal ,t[?] The next one is with p[j+1] Compare ,next[i+1]=j+1
for example next[6]=3 , Mode string slave 0-5 In this substring , The head and tail can match
Small string from 0 Start the subscript at the end of this small string Move back a bit

In fact, we can also find , KMPKMP The reason why the algorithm is fast , Not just because of its mismatch handling scheme , More importantly, it takes advantage of the characteristics of prefix and suffix , Never look for again and again , We can see that there is only one loop for matching in the code , in other words KMPKMP The algorithm has a “ Optimal history processing ” The nature of , And this property is also based on KMP The core idea of .

t[?] And p[0] All matching failed ,
-1 It means that this point in the main string cannot succeed , The main string moves back a position
Put the front of the pattern string to the failed position Continue matching

If it's with $p[x](x!=0)$ Comparison failed , that t[?] And next[x] matching

This form can successfully obtain the matching position , But there is one flaw ,next The array does not correctly reflect The real length of the small string that matches the beginning and end of the pattern string
There is no defect , Compare according to observation , Find out next【i】$i\in (0——p.size()-1)$ Represents the pattern string before i Characters , namely 0~ i-1 The beginning and end of this paragraph match the length of the small string , But 0~p.size()-1 The beginning and end of the whole pattern string match, but the length of the small string is unknown . Observe getNext（） Right in the function next The evaluation of array can find ,next The length of the array is $p.size()+1$ instead of $p.size()$, That is, being $next[p.size()]$, Can be said 0~p.size()-1 The whole pattern string matches the length of the small string .

【 Templates 】KMP string matching

【 Templates 】KMP string matching

#include <iostream>
#include <algorithm>
using namespace std;
const int N=1e6+5;
int next[N];
void getNext(string p){
    
	next[0]=-1;
	int i=0;
	int j=-1;
	// In the pattern matching string, in the small string that matches the beginning and end ,i Point to the last character of the tail string 
// j Point to the last character of the first string ,
//  That is to say p[i+1] The position of pointer backtracking when it does not match  j+1 It depends on it j location  
	int len=p.size();//strlen 
	while(i<len){
    
		if(j==-1||p[i]==p[j]){
    
			i++;j++;// The first and last strings still match, and then continue to move forward 
			next[i]=j;// Equivalent to p[i]=p[j] be next[i+1]=j+1 
// as for j==-1, That is, the pointer goes back from -1 Start comparing ,p[i+1] It must be from j==0 Start comparing 
 
		}
		else{
    
			j=next[j];// If p[i]！=p[j], that  p[i] Just like next[j] Compare  
		} 
	} 
}
void kmp(string t,string p){
    
	int lt=t.size();
	int lp=p.size();
	int i=0;
	int j=0;
	while(i<lt&&j<lp){
    
		if(j==-1||t[i]==p[j]){
    
			i++;
			j++;
		}
		else j=next[j];// such j It could be -1, Then I thought if To judge j==-1 
		//j==-1 Mode string slave 0 At the beginning j++,t[i] It is impossible to p[0] matching  
		if(j==(lp)){
    
		cout<<i-lp+1<<endl;
		j=next[j];// Go back to p【0】
	}	
}	
} 
int main(){
    
	string t;
	string p;
	cin>>t>>p;
	getNext(p); 
 	kmp(t,p);
 	for(int i=1;i<=p.size();i++){
    
	 //next The array length is p.size()+1,
//  after p.size() The first value is the length of the matching string in the pattern string  
 		cout<<next[i]<<" ";
	 }

    return 0;
}

There is another way to write , avoid next Value taking -1 Of

#include<iostream>
#include<cstring>
#define MAXN 1000010
using namespace std;
int next[MAXN];
int la,lb,j; 
char a[MAXN],b[MAXN];
int main()
{
    
    cin>>a+1;
    cin>>b+1;
    la=strlen(a+1);
    lb=strlen(b+1);
    for (int i=2;i<=lb;i++)
	   {
         
	   while(j&&b[i]!=b[j+1])
        j=next[j];    
       if(b[j+1]==b[i])j++;    
        next[i]=j;
       }
    j=0;
    for(int i=1;i<=la;i++)
	   {
    
          while(j>0&&b[j+1]!=a[i])
           j=next[j];
          if (b[j+1]==a[i]) 
           j++;
          if (j==lb) {
    cout<<i-lb+1<<endl;j=next[j];}
       }

    for (int i=1;i<=lb;i++)
    cout<<next[i]<<" ";
    return 0;
}