关于KMP算法的学习

   我不喜欢阅读长篇的还夹杂着数学公式的逻辑分析，所以看到很多讲解KMP算法的资料，觉得挺伤脑筋的，但花了挺长时间尝试学习KMP算法，KMP算法的思路是明白了，但是编程实现它可能还有点晕，参考了一些资料，它们的next数组有几种版本，有些是从下标0开始，有的是从下标1开始。

   一、我的尝试版

   现在有一个子串t="aabacaaabaabba"

   当在t[0]处匹配失败时，下一次匹配还是从0开始匹配，所以next[0]=0.

   当在t[1]处匹配失败时，t[1]的前缀只有一个a,所以下一次匹配还是从下标0处开始，因而next[1]=0。

   当在t[2]处匹配失败时，t[2]的前缀有一对元素匹配，所以下一次匹配从下标1处开始，因而next[2]=1。

   当在t[3]处匹配失败时，t[3]的前缀没有对称元素，所以下一次匹配从下标0处开始，因而next[3]=0。

   当在t[4]处匹配失败时，t[4]的前缀有一对元素对称，所以下一次匹配从下标1处开始，因而

next[4]=1。

   当在t[5]处匹配失败时，t[5]的前缀没有元素对称，所以下一次匹配从下标0处开始，因而

next[5]=0。

   当在t[6]处匹配失败时，t[6]的前缀有一对元素对称，所以下一次匹配从下标1处开始，因而

next[6]=1。

   当在t[7]处匹配失败时，t[4]的前缀有两对元素对称，所以下一次匹配从下标2处开始，因而

next[7]=2。

   同理，我们可以分析出后面的next元素。

   next数组填充元素过程我们知道了，但是还只是停留在理论上，真正地编程实现算法还需要更多考虑。下面是结合我自己的想法实现的求next数组的算法。

void get_next(char *t, char *next)
{
    int i, j;
    int tlen = strlen(t);
    i = 1;    j = 0;
    next[0] = 0;    next[1] = 0;
    while(i < tlen)
    {
        if(t[i] == t[j])
        {
            i++;    j++;
            next[i] = j;
        }
        else{
            if(j == 0)
            {
                i++;
                next[i] = j;
            }
            j = next[j];
        }
    }
}

   循环执行的次数与子串的长度和字符重复情况有关系，时间复杂度为O(n)。

   匹配算法如下：

int get_index(char *s, char *t, int pos)
{
    char *next;
    int slen, tlen, i, j;
    slen = strlen(s);
    tlen = strlen(t);
    next = (char*)malloc(sizeof(tlen)+1);
    get_next(t, next);
    i = pos;
    j = 0;
    while(i < slen && j < tlen)
    {
        if(s[i] == t[j] )
        {
            i++;   j++;
        }
        else{
            if(j==0)
                i++;
            j = next[j];
        }
    }
    if(j >= tlen)
        return (i-tlen);
    else
        return 0;
}

   时间复杂度为O(n+m)。

   二、教科书版

   我们数据结构课程时，用的课本是清华大学出版社出版，严蔚敏和吴伟民编写的数据及结构（C语言版），真心没搞懂分析过程。

   求next数组算法：

void get_nextval(char *t, int nextval)
{
    i= 0;
    nextval[1] = 0;
    j = 0;
    while(i < t[0])
    {
        if(j ==0 || t[i] == t[j])
        {
            i++;    j++;
            if(t[i] != t[j])
                nextval[i] = j;
            else
                nextval[i] = nextval[j];
        }
        else
            j = nextval[j];
    }
}

   那本书上给出了两个求next数组的算法，不过get_nextval更优。t[0]存放的是t串的字符个数。下面的s串的s[0]的字符个数。

   模式匹配算法：

int index_KMP(char *s, char *t, int pos)
{
    i = pos;    j = 1;
    while(i <= s[0] && j <= t[0])
    {
        if(j == 0 && s[i] == t[j])
        {
            i++;    j++;
        }
        else
            j = next[j];
    }
                                                                                
    if(j > t[0])
        return i = t[0];
    else
        return 0;
}

   三、一个模式匹配程序

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
void get_next(char *t, char *next)
{
    int i, j; int count = 0;
    int tlen = strlen(t);
    i = 1;
    j = 0;
    next[0] = 0;
    next[1] = 0;
    while(i < tlen)
    {
        count++;
        if(t[i] == t[j])
        {
            i++;
            j++;
            next[i] = j;
        }
        else{
            if(j == 0)
            {
                i++;
                next[i] = j;
            }
            j = next[j];
        }
    }
    next[tlen] = ‘\0‘;
    printf("count:%d\n", count);
}
int get_position(char *s, char *t, int pos)
{
    char *next;
    int slen, tlen, i, j;
    slen = strlen(s);
    tlen = strlen(t);
    next = (char*)malloc(sizeof(tlen)+1);
    get_next(t, next);
    i = 0;
    j = 0;
    while(i < tlen)
    {
        printf("next[%d] = %d\n", i, next[i]);
        i++;
    }
     i = pos;
    while(i < slen && j < tlen)
    {
        if(s[i] == t[j] )
        {
            i++;
            j++;
        }
        else{
            if(j==0)
                i++;
            j = next[j];
        }
    }
    if(j >= tlen)
        return (i-tlen);
    else
        return 0;
}
void main()
{
    char *s = "aaabaaaaaaaabbbababacbacbab";
    char *t =  "aabacaaabaabba";
    int pos, index;  
    index = get_position(s, t, pos);
    printf("index: %d\n", pos);
}

关于KMP算法的学习,布布扣,bubuko.com

关于KMP算法的学习

原文：http://slientradio.blog.51cto.com/7241495/1403145