KMP算法c++

Next数组

• 用于在模式字符串（Pattern）与目标字符串（Text）进行匹配时，当遇到不匹配的情况，指导模式字符串如何移动，以避免从头开始匹配，从而提高匹配效率。
• Next数组的构建是基于模式字符串的前缀和后缀的匹配。对于模式字符串中的每个位置i，Next数组记录了在该位置之前的子串中，最长的相同前缀后缀的长度。这个长度可以用来决定在失配时，模式字符串应该回退到哪个位置。

手工求next值

• 数组从下标1开始，用下面的方法。
  
• 数组从下标0开始，则初始化时next[0]=-1,公式为next[i]=匹配字符的个数。注意与下标从1开始的区别。
  

Next数组代码构建

代码

void getNext(const char* t,int* next){
	int j=-1;
	int i=0;
	next[0]=-1;
	while(i<=strlen(t)){
		if(j==-1 || t[i]==t[j]){
			i++;
			j++;
			if(t[i]!=t[j]){
				next[i]=j;
			}else{
				next[i]=next[j];
			}
		}else{
			j=next[j];
		}
	}
} 

kmp算法

算法

• KMP（Knuth-Morris-Pratt）算法是一种用于字符串匹配的算法，它通过预处理模式字符串（即要搜索的字符串）来创建一个部分匹配表（也称为"next"数组），从而在主字符串（即被搜索的字符串）中快速搜索模式字符串的出现。KMP算法的核心思想是，当发生不匹配时，利用已经匹配的部分信息，避免从头开始匹配。
• KMP算法的步骤：

1. 创建Next数组：
   初始化两个指针i和j，分别指向模式字符串的当前字符和Next数组的当前位置。
   遍历模式字符串，对于每个字符，找出它之前的所有相同前缀后缀的最长长度，将其存入Next数组。
2. 字符串匹配：
   使用两个指针i和j分别遍历主字符串和模式字符串。
   当j指向的模式字符串字符与i指向的主字符串字符相等时，两个指针同时后移。
   当字符不匹配时，如果j不为0，则将j移动到Next数组中j所指向的值，即跳过已经匹配的前缀。
   如果j为0，则只将i后移，继续匹配。

代码

#include<iostream>
#include<cstring>
using namespace std;
/*
i表示后缀
j表示前缀，以及前、后缀适配的最大长度 
*/
void getNext(const char* t,int* next){
	int j=-1;
	int i=0;
	next[0]=-1;
	while(i<=strlen(t)){
		if(j==-1 || t[i]==t[j]){
			i++;
			j++;
			if(t[i]!=t[j]){
				next[i]=j;
			}else{
				next[i]=next[j];
			}
		}else{
			j=next[j];
		}
	}
} 
//s主串，m模式串 
int kmp(const char* s,const char* m){
	int next[1000];
	getNext(m,next);
	int i=0,j=0;
	while(i<strlen(s) && j<strlen(m)){
		if(s[i]==m[j]){
			i++;
			++j;
		}else{
			j=next[j];
			if(j<0){
				i++;
				j=0; 
			}
		}
	}
	if(j==strlen(m))
		return i-strlen(m);
	return -1;
} 
int main(){
	cout<<kmp("aaaaaaabaaaxxxyyyy","aaab")<<endl;
	cout<<kmp("acsxweddaaaaaabxxxy","aaac")<<endl;
	cout<<kmp("kaaaaaaabaaxxxy","aaa")<<endl;
	cout<<kmp("aaaabaaac","aaac")<<endl;
	return 0;
}