KMP算法数组下标从0和数组下标从1开始

2023-12-15 01:48:00

我在运用KMP时,总时会搞混如果数组下标为0时要如何用写,下标为1时要如何写。

当下标为0时kmp

void kmp(int len)
{
	//下标为0 时
	vector<int> f(n,-1);
	for(int i = 1;i < len;i++)
	{ // 每次更新的是 下标i 
	//  当第 i+1不匹配是 跳到 f[i]的位置上,看小标为 s[f[i]+1] == s[i] 不等可以继续跳 
		int j = f[i-1];
		while(j != -1 && s[j+1] != s[i]){
			s[j] = f[j];
		}
		if(s[j+1] == s[i])
		{
			f[i] = j+1;
		}
		else{
			f[i] = j;
		}
	}
}

当下标为1时,KMP算法:

#include<iostream>
#include<cstring>
#define MAXN 1000010
using namespace std;
int kmp[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=kmp[j];    
       if(b[j+1]==b[i])j++;    
        kmp[i]=j;
       }
    j=0;
    for(int i=1;i<=la;i++)
	   {
          while(j>0&&b[j+1]!=a[i])
           j=kmp[j];
          if (b[j+1]==a[i]) 
           j++;
          if (j==lb) {cout<<i-lb+1<<endl;j=kmp[j];}
       }

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

其实基本一样的只是一个初始化为-1,一个初始化为0。而next中记录的意义为前缀字符串和后缀字符串的长度,当i+1不匹配时,可以跳到 next[i] (因为next[i] 在进行 next[i]+1 是否配对成功)

还有一种是 在 KMP 中是记录next[i+1]的下标。

void getNext(char *p,int plen)
{
	// 记录 i+1 的跳的位置 
	Next[0]	= 0;
	Next[1] = 1;
	for(int i = 2;i < plen;i++)
	{
		int j = Next[i];
		while(j&&p[i] != p[j])
		{
			j = Next[j];
		}
		if(p[i] == p[j])
		{
			Next[i+1] = j+1;
		}else{
			Next[i+1] = 0;
		}
	}
} 

这种Next是直接记录当i不匹配时,直接跳到下标为Next[i]进行配对,它记录的是Next 时最长前缀 和最长后缀的长度后 ,最长前缀的长度还+1。所以直接比较Next[i]就可以了。

文章来源:https://blog.csdn.net/zhi6fui/article/details/134933483
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。