字符串匹配之KMP实现

时间:2022-03-11 15:59:11

KMP算法看懂了觉得特别简单,思路很简单,看不懂之前,查各种资料,看的稀里糊涂,即使网上最简单的解释,依然看的稀里糊涂。

KMP算法充分利用了目标字符串ptr的性质(比如里面部分字符串的重复性,即使不存在重复字段,在比较时,实现最大的移动量)。

kmp算法主要是next数组的计算

代码分析:

 

#include <stdio.h>
#include
<string.h>
int next[32] = {-999};
void print_next(int next[], int n)
{
for (int i = 0; i < n; i++)
{
printf(
"next[%d] = %d\n", i, next[i]);
}
}
void getNext(char* arrays)
{
int i = 0,j = -1;
next[i]
= j;
while(i<strlen(arrays))
{
if(j==-1||arrays[i] == arrays[j])
{
i
++;
j
++;
next[i]
= j;
}
else
{
j
=next[j];
}

}

}

int KMP(char* arrays1,char * arrays2)
{
int i = 0,j = 0;
while(i<strlen(arrays1)&&j<strlen(arrays2))
{
if(arrays1[i]==arrays2[j]||j==-1)
{
i
++;
j
++;
}
else{
j
=next[j];}
}
if(j==strlen(arrays2)) return i - strlen(arrays2);
return -1;

}
int main(void)
{
char *s = "ababcabcacbab";
char *t = "abcac";
int index;
getNext(t);
print_next(next, strlen(t));
index
= KMP(s, t);
printf(
"index = %d\n", index);
}