黑马程序员技术交流社区

标题: 请教KMP算法.. [打印本页]

---

作者: 王东    时间: 2013-10-21 00:24
标题: 请教KMP算法..
今天看算法的时候，看到了KMP算法，虽然思路有，但是代码不知道从什么地方开始，请教各位大牛，谢谢谢谢。。。

---

作者: 龏鈊づ廱鵆ぐ    时间: 2013-10-21 08:08
KMP算法的思想就是：在匹配过程称，若发生不匹配的情况，如果next[j]>=0，则目标串的指针i不变，将模式串的指针j移动到next[j]的位置继续进行匹配；若next[j]=-1，则将i右移1位，并将j置0，继续进行比较。

代码实现如下：


int KMPMatch(char *s,char *p)
{
    int next[100];
    int i,j;
    i=0;
    j=0;
    getNext(p,next);
    while(i<strlen(s))
    {
        if(j==-1||s[i]==p[j])
        {
            i++;
            j++;
        }
        else
        {
            j=next[j];       //消除了指针i的回溯
        }
        if(j==strlen(p))
            return i-strlen(p);
    }
    return -1;
}

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2