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);
}