为方便 i,j 更清晰的移位,字符数组第一位丢掉不要,即序号从1开始
引子 – BF算法
主串S和模式串P匹配过程途中失败,则模式串指针 j = 1 (从头开始),主串指针需要回溯到 i = (i – j + 1) + 1 (本次匹配的初始位置 i0 + 1)。最坏的时间复杂度即为 (n – m) * m + m = (n – m + 1) * m = O(nm)
阿Q对KMP算法的理解
BF算法,每次都把 i 回溯,j 退为1(正常人都能想到)。但是在匹配过程中主串还需要要回溯嘛?如果回溯,之前匹配的信息是否没利用上了?
KMP算法好处就在于主串的指针是只增不减的,其当次匹配失败的位置的前K个字符(倒过来)如果和模式串的前K个字符是相同的,那本次匹配成功的就有K个字符,如下图:
由图可以看出下一次匹配启动时:主串的指针 i 不变,模式串逻辑上往后移动了 j – k (注意是逻辑上)。
那么关键在于哪呢?阿Q:在于模式串当前位置匹配失败后,下一次 j 应该去哪。【 next[j] ♥】
next[j]
注意:以下讨论的序号都是从 1 开始,若从零开始, next[j] = next[j] – 1
下面我们来个next[j]的题目,看图就理解了(做题人视角)
如果编写成程序呢?该怎么办?不可能说比 {aba}的前缀和后缀的交集吧(不服可以试试)
那接下来我们换种思路来考虑这个问题。(编程视角)
nextval(x)
编程任务(408统考不考KMP算法题)
阿Q备注:以下均用定长顺序存储实现 – SString(参考:串的存储)
1、编写 KMP算法(获取模式串 next[j] 和 nextval[j])
// C实现
// 假设先通过代码实现了next[j]的计算
// 数组下标从1开始,0不管
int Index_KMP(SString S, SString P, int next[]){
int i = 1, j = 1;
while(i <= S.length && j <= P.length) // 不超过上限
{
if(S.ch[i] == P.ch[j] || j == 0) ++i, ++j; // 阿Q备注:此时 j = 0 时,i也需要 + 1
else j = next[j];
}
// P找完了
if(j > P.length) return i - P.length;
else return 0;
}
// 下面才是重头戏,编程实现next[j]的计算
void get_next(SString P, int next[]){
next[1] = 0; // 规定
int i = 1, j = 0;
// 给 next 各项赋值
while(i < P.length)
{
/*
已知 next[j] 求 next[j + 1]
p.ch[next[j]] == p.ch[j] -> next[j + 1] = next[j] + 1
p.ch[next[j]] != p.ch[j] -> j = next[j] (递归) -> p.ch[k*] == p.ch[j]
j == 0 -> next[j+1] = next[1] + 1;
*/
if(j == 0 || P.ch[i] == P.ch[j]){
++i, ++j;
next[i] = j; //阿Q备注: j在此处为 k* + 1,在循环外始终为 k*
// 阿Q思考:经测试:next[i] = next[j] + 1 出错,问题在哪呢? 还是 j = k* + 1,不为 i -1
// 经测速 next[i] = next[i - 1] + 1 也出错,问题在哪呢? 因为i只增,next[2] = next[1] + 1 = 2 错误
}
else j = next[j];
}
}
// next的改进算法
void get_nextval(SString P, int nextval[]){
int i = 1, j = 0;
nextval[1] = 0; // nextval[1] = next[1]
/*
与next[j]不同点在于:
还需进一步判断 p.ch[next[j]] ?= p.ch[next[next[j]]]
*/
while(i < P.length){
if(j == 0 || P.ch[i] == P.ch[j]){
++i, ++j;
// 下面为不同点,需额外判断
if(P.ch[i] == P.ch[j]) nextval[i] = nextval[j];
else nextval[i] = j;
}
else j = nextval[j];
}
}
// 经测试,代码正确
2、模式串在主串中有多少个完全匹配的字串
// C实现
int count_total_index_KMP(SString S, SString P, int next[], int index[])
{
int i = 1, j = 1;
int count = 0; // 记录完全匹配的个数
// 下标从 1 ~ length
while (i <= S.length){
while(j <= P.length && i <= S.length){
if(S.ch[i] == P.ch[j] | j == 0) ++i,++j;
else j = next[j];
}
if(j > P.length){
count += 1;
// j 回溯到 1(从头比), i = i - P.length + 1
index[count] = i - P.length;
j = 1;
i = i - P.length + 1;
}
}
return count;
}
// 阿Q:上述函数是重点,以下为测试
int main(){
// 创建主串S和模式串P
SString S, P;
char *chs = "zaabaabbabaabaabbabaab"; // 第一位随意插值,下标从1开始
int slen = 21;
int i = 1;
for(;i <= slen;i++) S.ch[i] = chs[i];
S.length = slen;
char *chp = "zabaa";
int plen = 4;
for(i = 1; i <= plen; i++) P.ch[i] = chp[i];
P.length = 4;
int next[5];
get_next(P,next);
//P在S中完全匹配
//分段匹配即可,定一个数组记录各次匹配成功的位置。
//int index[MAXINDEXLEN];
/*
范围: 1->a1 ; a1 + 1->a2; ...; an-1 + 1 -> an; an + 1->MAXINDEXLEN
*/
// 需要临时创建一个SString temp 存放主串中未匹配的剩余字符串
// 每段匹配成功的pos + 当前匹配开头的位置 ak + 1
// 阿Q:上述当然可以,但最后能修改下 Index_KMP函数(更简洁)
// Index_KMP 函数 修改为 count_total_index_KMP 函数
int index[MAXINDEXLEN];
int count = count_total_index_KMP(S,P,next,index);
printf("%d\n", count);
for(int i = 1; i <= count; i++)
printf("%d ",index[i]);
return 0;
}
/*
输出:
4
2 8 11 17
*/
评论