公众平台如何做网站,汽车网络营销方式,wordpress storage,百度普通收录我在运用KMP时#xff0c;总时会搞混如果数组下标为0时要如何用写#xff0c;下标为1时要如何写。
当下标为0时kmp
void kmp(int len)
{//下标为0 时vectorint f(n,-1);for(int i 1;i len;i){ // 每次更新的是 下标i // 当第 i1不匹配是 跳到 f[i]的位置上总时会搞混如果数组下标为0时要如何用写下标为1时要如何写。
当下标为0时kmp
void kmp(int len)
{//下标为0 时vectorint f(n,-1);for(int i 1;i len;i){ // 每次更新的是 下标i // 当第 i1不匹配是 跳到 f[i]的位置上看小标为 s[f[i]1] s[i] 不等可以继续跳 int j f[i-1];while(j ! -1 s[j1] ! s[i]){s[j] f[j];}if(s[j1] s[i]){f[i] j1;}else{f[i] j;}}
}
当下标为1时KMP算法
#includeiostream
#includecstring
#define MAXN 1000010
using namespace std;
int kmp[MAXN];
int la,lb,j;
char a[MAXN],b[MAXN];
int main()
{cina1;cinb1;lastrlen(a1);lbstrlen(b1);for (int i2;ilb;i){ while(jb[i]!b[j1])jkmp[j]; if(b[j1]b[i])j; kmp[i]j;}j0;for(int i1;ila;i){while(j0b[j1]!a[i])jkmp[j];if (b[j1]a[i]) j;if (jlb) {couti-lb1endl;jkmp[j];}}for (int i1;ilb;i)coutkmp[i] ;return 0;
}
其实基本一样的只是一个初始化为-1一个初始化为0。而next中记录的意义为前缀字符串和后缀字符串的长度当i1不匹配时可以跳到 next[i] (因为next[i] 在进行 next[i]1 是否配对成功)
还有一种是 在 KMP 中是记录next[i1]的下标。
void getNext(char *p,int plen)
{// 记录 i1 的跳的位置 Next[0] 0;Next[1] 1;for(int i 2;i plen;i){int j Next[i];while(jp[i] ! p[j]){j Next[j];}if(p[i] p[j]){Next[i1] j1;}else{Next[i1] 0;}}
}
这种Next是直接记录当i不匹配时直接跳到下标为Next[i]进行配对它记录的是Next 时最长前缀 和最长后缀的长度后 最长前缀的长度还1。所以直接比较Next[i]就可以了。
