写在前面
考408期间学习的时候看到的bilibili的视频先附上:
链接: link
这个视频主要应付考试,没有讲代码的思路,这里我就顺着这个视频的思路,写出代码,思路如有不清晰之处,望指出,并且可以看看这个视频。
思路
以此为例:
观察我们可以知道先求出maxL,maxL是以当前字符结尾的匹配串。
计算方法:
第一个默认为0,第二个如果和第一个相同为1,不同为0(这里的b和a不同因此为0)。
往后的序列,可以按照以下方法计算:(由于string默认从0开始,因此上面的序号在代码中也是从0开始而不是从1开始)
由于前面的字符一定是以前面的字符为结尾的匹配字串,因此如果当前字符可以与前面一个字符匹配的字符下一个相同,则maxL[i]=maxL[i-1]+1;也就是上一个数得到next数组的+1。
如果不相同,就看当前字符与第一个字符相同不相同,相同则当前字符作为字串的开头,即为1,如果不同则为0;
如果上面看不懂就直接看例子:
如4号为的a,他的前面是3号位的a,maxL[3]=1,找到1号位的下一位2号位,是b,由于a和b不同。则判断a和字符串开头是否相同,因为都相同所以为1。
求出来maxL以后,左侧添加-1,向右平移再逐项+1(由于开头本来就是0,因此next[0]=maxL[0]这里不需要动)剩下的一个循环解决:
for(int i =s.length()-1;i>0;i--){
next[i]=next[i-1]+1;
}
代码
当然你如果觉得我的代码写的贼丑,自己改改就好了
#include<stdio.h>
#include<string>
#include<iostream>
using namespace std;
int next[100];
void getnext(string s){
next[0]=0;
for(int i =1;i<s.length();i++){
if(i==1){
if (s[1]==s[0]) next[1]=1;
else next[1]=0;
}
if(s[i]==s[next[i-1]]) next[i]=next[i-1]+1;
else if (s[i]==s[0]) {
next[i]=1;
}
else{
next[i]=0;
}
}
for(int i =s.length()-1;i>0;i--){
next[i]=next[i-1]+1;
}
}
int main(){
string s;
cin>>s;
getnext(s);
for(int i =0;i<s.length();i++)
printf("%d ",next[i]);
}
运行结果图
视频中的例子:
王道数据结构kmp的题6:
均正确