KMP算法 完全看不懂唉,该怎么处理
KMP算法 完全看不懂唉
虽然按算法书上的算法把代码写出来了 但是无法理解 也不知道怎么记忆这个写法哎
有谁能推荐下记住这个算法的写法的方法么
------解决思路----------------------
求子串的Next数组
void getNext(char *str, int *next)
{
assert(str != NULL && next != NULL);
int size = strlen(str);
if(size == 0)
return;
int i = 0;
int k = -1;
next[0] = -1;
while(i < size - 1)
{
if(k == -1
------解决思路----------------------
str[i] == str[k])
{
i++;
k++;
if(str[i] == str[k])
{
next[i] = next[k];
}
else
{
next[i] = k;
}
}
else
{
k = next[k];
}
}
}
------解决思路----------------------
http://blog.****.net/yutianzuijin/article/details/11954939
这个建议楼主仔细看看 说的还是比较清楚的
------解决思路----------------------
静下心好好分析
虽然按算法书上的算法把代码写出来了 但是无法理解 也不知道怎么记忆这个写法哎
有谁能推荐下记住这个算法的写法的方法么
#include <stdio.h>
#include <malloc.h>
int kmp_table(const unsigned char * W,int len,int* T)
{
if(!W||!T) return 1;
int pos=2,cnd=0;
T[0]=-1,T[1]=0;
while( pos<len ){
if( W[pos-1]==W[cnd] ){
cnd=cnd+1,T[pos]=cnd,pos=pos+1;
}
else if( cnd>0 ){ cnd=T[cnd]; }
else{ T[pos]=0;pos=pos+1; }
}
return 0;
}
int kmp_search(const unsigned char * S,const unsigned char * W,int sLen,int wLen)
{
int m=0,i=0;
int *T=(int*)malloc(wLen*sizeof(int));
kmp_table( W,wLen,T);
while( m + i < sLen ){
if( W[i] == S[m+i] ){
if( i==wLen-1 ) { free(T);return m; }
i++;
}
else{
if( T[i] > -1 ) { m=m+i-T[i], i=T[i]; }
else{ i=0, m++; }
}
}
free(T);
return sLen;
}
int main()
{
int n=kmp_search( (const unsigned char *)"bcaaaaa",(const unsigned char *)"aaa",5,3);
printf("%d\n",n);
return 0;
}
------解决思路----------------------
求子串的Next数组
void getNext(char *str, int *next)
{
assert(str != NULL && next != NULL);
int size = strlen(str);
if(size == 0)
return;
int i = 0;
int k = -1;
next[0] = -1;
while(i < size - 1)
{
if(k == -1
------解决思路----------------------
str[i] == str[k])
{
i++;
k++;
if(str[i] == str[k])
{
next[i] = next[k];
}
else
{
next[i] = k;
}
}
else
{
k = next[k];
}
}
}
------解决思路----------------------
http://blog.****.net/yutianzuijin/article/details/11954939
这个建议楼主仔细看看 说的还是比较清楚的
------解决思路----------------------
静下心好好分析