算法--kmp字符串匹配算法

简单介绍

kmp算法是一种字符串匹配算法，用来判断字符串A是否在字符串B中。
kmp是由Knuth,Moriis和Pratt三个人设计，所以称为kmp算法。
kmp是一个高效的算法，而普通的字符串匹配每次循环遍历所以复杂度为O(mxn)
而kmp算法的时间复杂度，理论上是O(n)

普通匹配算法

char *str_match(const char *str1, const char *str2){

    int i = 0;
    int j = 0;
    int length1 = 0;
    int length2 = 0;
    char *result = NULL;
    length1 = strlen(a);
    length2 = strlen(b);
    for(i = 0; i < length1; ++i){
        for(j = 0; j < length2; ++j){
            if(a[i + j] != a[j]){
                break;
            }
        }
        if(j == length2){
            result = (char *)str1 - j;
            break;
        }
    }
    return result;
}

kmp算法思路

kmp也需要两个指针，分别指向两个字符串，普通的匹配算法。上面的代码是以
偏移量来对字符串进行遍历，当匹配失败，str1的偏移需要回退到之前开始的
下一个字符开始遍历。上面的代码并没有减法，因为对于str1的偏移是i+j，
str2的偏移是j，每次j重新变为0，就相当于回退了。然而，kmp算法并不会
回退str1的偏移量，只会回退str2的偏移量。
那么问题来了，如果回退str2的偏移量，该回退多少？
举两个极端的例子：
用m表示str1的偏移量，n表示str2的偏移量
str1 abcdefabcdefghijklmn
str2 abcdefg
当第一次比到g，发现不相等，那么需要回退到a，也就是字符串的开头，而str1
并不需要移动，因为之前的字符是不可能会匹配段里面的。
str1 aaaaaaaaaaaaaab
str2 aaab
当第一次比较到b，发现不相等，此时m=3,n=3,现在就需要回退str2的偏移，只回退1
n=2,将它与m对应的字符比较，发现相等，继续下一个。这里偏移只要回退1，因为已经
到b，说明前面都是aaa，即使m=3对应的字符不是b，但是有可能是a，所以此时，m=3
前面的两个字符是有可能是匹配段的。
所以，kmp的关键就是如何来求str2在不匹配的时候该向前偏移多少，也就是求str2的next数组
在面试题中一般有求一个字符串的next数组。

求字符串的next数组

next数组里面存的是什么？
当匹配失败的时候，应该回退到第几个字符？
a a a a a a b
-1 0 1 2 3 4 5

如果用i指向str1(较长的)，j指向str2(较短的)
1.在匹配的过程中分两种情况，匹配第一个字符(这里的第一个字符指str2的第一个字符)，
匹配后面的字符.
在匹配的过程中是这样的：
如果是第一个，匹配i++,j++,如果不匹配，i++,j不动。
如果是中间的，匹配i++,j++,如果不匹配，i不动，j要变成next[j]，也就是后移,后移多少不用管，
只要移动到这，说明就能保证前面的字符是匹配的。

2.那怎样设置next的值，第一个比较特殊，需要特殊标记，所以设置成-1。而后面的，至少都是跳转到0，所以不可能
为负的，以abcdabce为例
a b c d a b c e
0 1 2 3 4 5 6 7
-1 0 0 0 0 1 2 3
也许这个例子有点问题，因为下标为5元素是b，如果b不匹配，就没必要比较下标为1的元素了。
但是，以next的计算方式，下标为5的next值与它本是是什么值并没有关系。他的值为1，只因为
他的前一位是a，所以在不匹配的时候就不需要比较第一位的a，直接比第二2位。
求某一位的next值，就要看它前面最多有多少连续的端和开头匹配。
下标为6的前面有ab和开头的ab匹配，所以为2
下标为7的前面有abc与开头的abc匹配，所以为3
求传入str，求next数组的代码
首先下标为0的是-1，下标为1的一定是0。然后开始递推。
之后的下标求next值，以下标为n为例，现在已知next[n-1]，如果n-1对应的值和next[n-1]对应的值
是相等的话那么next[n]=next[n-1] + 1;但是如果不相等呢？直接变为0？并不是这样。
以abctabcdabctabct为例
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
a b c t a b c d a b c t a b c t c
-1 0 0 0 0 1 2 3 0 1 2 3 4 5 6 7 4
下标为16的前一位15对应的t，他的next为7对应d，并不相等
需要进一步判断t与7的next,也就是3对应的是否相等，相等，所以next[16]=next[7]+1;

void get_next(int *next, char *str){

    int length = 0;
    int i = 0;
    int j = 0;
    int k = 0;
    length = strlen(str);
    for(i = 0; i < length; ++i){
        if(i == 0){
            next[i] = -1;
            continue;
        }
        if(i == 1){
            next[i] = 0;
            continue;
        }
        k = i - 1;
        while(k > 0){
            if(str[i - 1] == str[next[k]]){
                next[i] = next[k] + 1;
                break;
            }else{
                k = next[k];
            }
        }
        if(k == 0){
            next[i] = 0;
        }
    }
}

字符串匹配

char *str_match(const char *str1, const char *str2)
{
    int i = 0;
    int j = 0;
    int length1 = 0;
    int length2 = 0;
    length1 = strlen(str1);
    length2 = strlen(str2);
    while(i < length1){
        if(str[i] == str[j]){
            i++;
            j++;
        }else{
            if(next[j] < 0){
                j++;
            }else{
                j = next[j];
            }
        }
        if(j == length2){
            return str1 + i - j;
        }
    }
}