首页
登录 | 注册

KMP算法死记硬背

由于本人才疏学浅,KMP算法写法简单却极难理解,本人只好来硬的。

#include<stdio.h>
#include<stdlib.h>
void getNext(char *p,int *next)
{
    int j,k;
    next[0]=-1;
    j=0;
    k=-1;
    while(j<strlen(p)-1)
    {
        if(k==-1||p[j]==p[k])    //匹配的情况下,p[j]==p[k]
        {
            j++;
            k++;
            next[j]=k;      
        }
        else       		 //p[j]!=p[k]
            k=next[k];
    } 
}
int kmp_search(char *src,int slen,char *patn,int plen)
{
	int next[100];
	int i = 0;
	int j = 0;
	getNext(patn,next);
	while(i<slen&&j<plen)
	{
		if(j==-1||src[i]==patn[j])
		{
			i++;
			j++;
		}
		else
		{
			j = next[j];
		}
	}
	if(j==plen)
		return i-j;
	return -1;
}
int main(int argc,char *argv[])
{
	char a[128] = "ababcabcacbab";
	char b[128] = "abcac";
	printf("%d\n",kmp_search(a,strlen(a),b,strlen(b)));
	return 0;
}




2020 jeepxie.net webmaster#jeepxie.net
10 q. 0.008 s.
京ICP备10005923号