字符串匹配--KMP

字符串匹配

思路： nxt[j]=k的意思是，下标为j的字符前字符串的最长相等前后缀为k nxt数组的值只与子串有关 nxtv则是优化nxt 使得处理时间更加短

时间复杂度O(n)

Code:

#include<iostream>
#include<memory.h>
#include<string.h>
#include<string> 
using namespace std;
const int N=1e6+5;
int nxt[N];
int nxtv[N];
int strl,subl;
char str[N],sub[N];
void getnext(char *s)
{
	nxt[0]=-1;//默认下标0的值为-1
	int j=0,k=-1;//没有匹配的时候 k=-1
	while(j<=subl)
	{
		if(k==-1||sub[j]==sub[k])//如果两个字符相等
		{
			j++;k++;//j和k自增
			nxt[j]=k;//nxt数组j的值为k
		}
		else
		{
			k=nxt[k];//如果k不为起点 且两个字符不相等  则k赋值为nxt数组k下标的值
		}
	}
}

void getnextv(char *sub)//优化nxt
{
	nxtv[0]=-1;//默认0下标的值为-1
	for(int i=1;i<subl;i++)//遍历字符串
	{
		if(sub[i]!=sub[nxt[i]])//如果字符串i下标和nxt[i]下标的值不一样 则nxtv=nxt
		nxtv[i]=nxt[i];
		else //如果相同 那就值就回到第一个sub[i]出现的地方
		nxtv[i]=nxtv[nxt[i]];
	}
}
void kmp(char *s,char *subs)
{
	int i=0,j=0;
	while(i<strl&&j<subl)//两个字符串均不超过其最大长度
	{
		if(j==-1||str[i]==sub[j])//如果j值为起始点  或者两个字符相等 则i，j自增
		{
			i++;j++;
		}
		else j=nxtv[j];//如果不相等 则回到上一轮的位置
		if(j==subl)//如果子串以及匹配完 
		{	
			cout<<i-subl+1<<endl;//输出子串的位置
			i=i-subl+1;//更新母串的下标
			j=-1;	//更新子串的下标
		}
	}
	
}


int main()
{

	cin>>str;//读入母串str
	cin>>sub;//读入子串sub
	strl=strlen(str);//母串长度
	subl=strlen(sub);//子串长度
	getnext(sub);
	getnextv(sub);
	kmp(str,sub);
	cout<<strl<<" "<<subl<<endl;
	for(int i=1;i<=subl;i++)
	cout<<nxt[i]<<' ';
	return 0;
}