Example of KMP algorithm

KMP algorithm is a pattern matching algorithm jointly proposed by Knuth, Morris and Pratt. For any pattern and target sequence, KMP algorithm can complete matching search in linear time without degradation. It is a very excellent pattern matching algorithm.

Analysis: the key of KMP is to find the value of next, preprocess the value of next first, and then scan it once. The complexity is O (m+n).

Example code:

#include<stdio.h>
#include<string.h>
#define N 1000005
int s[N];
int p[N];
int next[N];
int m,n;
void getnext(){
 int j=0,k=-1;
 next[0]=-1;
 while(j<m){
  if(k==-1||p[j]==p[k]){
   j++;
   k++;
   next[j]=k;
  }
  else
   k=next[k];
 }
}
int kmp(){
 int i=0,j=0;
 getnext();
 while(i<n){
  if(j==-1||s[i]==p[j]){
   i++;
   j++;
  }
  else
   j=next[j];
  if(j==m)
   return i;
 }
 return -1;
}
int main(){
 int t;
 scanf("%d",&t);
 while(t--){
  scanf("%d%d",&n,&m);
  for(int i=0;i<n;i++)
   scanf("%d",&s[i]);
  for(int i=0;i<m;i++)
   scanf("%d",&p[i]);
  if(kmp()==-1)
   printf("-1\n");
  else
   printf("%d\n",kmp()-m+1);
 }
 return 0;
}

The above is the example of KMP algorithm on the data structure and algorithm of the site there are a lot of articles, I hope you search, thank you for reading, hope to help you, thank you for the support of the site!