KMP算法总结

/*
 * KMP 算法一直以来都是我不好理解的算法之一
 * 不好理解主要是有几个考量，这个算法只要我有一段时间不去接触它，我就会遗忘
 * 不知道如何再复现这个算法。究其本质原因还是个人对这个算法得理解不深刻
 * 最近这段时间，我一直从一个初学者的角度来思考这个算法的本质性的问题
 * 我不用画图，一旦使用了图形就意味着理解的程度肯定是上了一个层次，
 * 线性的理解方式，是最自然的方式。
 * 
 * KMP算法是在朴素字符串的匹配方法上进行的修正，当子串和主串的某个字符匹配失败后，
 * 子串的游标回退到0("当前游标的位置-刚刚匹配的字符数")，主串的游标回退到当前"游标的位置-刚刚匹配的字符数+1"的位置上。
 * 如果不理解这个过程，你可以简单的编写一个朴素的算法，我相信这个算法大部分的人都
 * 能理解，因为他是线性思维思考的算法
 *
 * KMP针对的算法就是主串游标的回退的问题！从上面的公式中我们会发现，我们很关心"刚刚匹配的字符数"，
 * 这也是KMP算法要解决的核心问题，我们KMP算法中的NEXT表的作用就是为这个服务的。
 * NEXT表的计算使用子串的性质，这里，我们关心子串中到底有没有前缀包含的问题。
 * 所有围绕KMP算法的核心就是子串中有前缀包含，而朴素算法的回退问题就是前缀包含问题导致的
 *
 * 先来说一个没有前缀包含的的子串"abcd"， 这子串就是一个没有前缀包含的子串
 * 对于这个子串来说，我们可以改进它的子串匹配算法。
 *  当子串游标为0的时候，子串和主串字符匹配失败，主串游标+1
 *  其他情况，当主串和子串字符匹配失败的的时候，子串游标设置为0，主串游标不变
 * 从算法中我们看到对于没有前缀包含的情况时候，我们不会需要什么NEXT表，也可以实现类似的KMP算法
 * 从后面的NEXT表的构建过程中，上述算法只是KMP算法的特例
 *
 * 含有前缀包含的子串"abcabcacab"，  这是一个含有前缀包含的子串
 * 这也是我们的主要研究对象，其中最长的前缀包含是"abca"
 *  abc-abca-cab
 *      abca-bcacab
 * 我们之所以考虑最长的前缀子串是因为，我们只关心匹配失败的时候会出现的情况，最长前缀之后的第一个字符就是匹配失败的字符
 * 针对这个位置，我们的跳转位置就是我们关心的，假设字符从0开始计数，我们知道NEXT[7] = 4。
 * 还有两个位置需要我们考虑：
 *  第一个位置：第一个匹配的字符成功的时候，我们的NEXT的对应值应该是一个特殊的值，这里使用-1，-1表示主串的游标需要加1，子串的游标设置为0
 *  第二个位置：前缀匹配上的其他字符的NEXT值的问题，这里我们设置NEXT值为0
 * 算法中还有一种CASE需要考虑，如果第一个前缀的第一个字符匹配失败了，NEXT值为多少，这里我们设置NEXT值为0，这是没有前缀包含的时候的情况
 *
 * 依据上述的算法，我们知道NEXT表的值为：-1,0,0,-1,0,0,0,4,-1,0
 *
 * 说实在话，说了这么多自己还是一知半解，如果有更好的理解方式，我希望我可以改进
 *
 * 计算机的算法不应该只能被少数人理解，它是一种做事的方法，这个方法应该尽可能的通俗（线性逻辑算法）
 *
 * */

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

/*
 * 这个编码形式不是最简的
void
CalNEXT(const char * T, int * NEXT, int T_L)
{
    int i;
    int j;

    NEXT[0] = -1;

    i = 1;
    j = 0;
    while (i < T_L) {
        if (j == 0) {
            if (T[i] == T[j]) {
                NEXT[i] = -1;
                ++i;
                ++j;
            } else {
                NEXT[i] = 0;
                ++i;
                j = 0;
            }
        } else if (T[i] == T[j]) {
            NEXT[i] = 0;
            ++i;
            ++j;
        } else {
            NEXT[i] = j;
            ++i;
            j = 0;
        }
    }
} */

void
CalNEXT(const char * T, int * NEXT, int T_L)
{
    int i;
    int j;

    NEXT[0] = -1;

    i = 1;
    j = 0;
    while (i < T_L) {
        if (T[i] == T[j]) {
            NEXT[i] = (j==0 ? -1 : 0);
            ++i;
            ++j;
        } else {
            NEXT[i] = j;
            ++i;
            j = 0;
        }
    }
}

int
KMP_GetStrIndex(const char * S, const char * T)
{
    int S_L = strlen(S);
    int T_L = strlen(T);
    int i;
    int j;

    int *   NEXT    = (int *)malloc(sizeof(int) * T_L);
    CalNEXT(T, NEXT, T_L);

    i = 0;
    j = 0;
    while (i < S_L && j < T_L) {
        if (S[i] == T[j]) {
            ++i;
            ++j;
        } else {
            j = NEXT[j];
            if (j == -1) {
                ++i;
                j = 0;
            }
        }
    }

    return j == T_L ? i-j : -1;
}

int
main(int argc, char ** argv)
{
    char    main_str[] = "abaacabcabcabcacababc";
    char    child_str[] = "abcabcacab";
    int nIndex;     // child_str 在 main_str中的索引值，-1表示不再主串中

    nIndex = KMP_GetStrIndex(main_str, child_str);
    printf("%d\n", nIndex);

    exit(0);
}