【问题】给了一个文本串和模式串，要求模式串在文本串中第一次出现的位置？

【前期准备】原来看kmp的时候总是看不懂，归根结底是没有理解Next数组的含义，今天再次学习kmp竟然对next秒懂了，现将算法学习记录如下！！

【算法描述】

一 kmp算法为什么比传统的字符串匹配算法快

假设文本T = y1y2y3....yn， 模式 P = p1p2p3...pm， 传统的匹配算法把位移为0,1,...n-m时的文本依次跟P比较，每次比较最多花费O(m)的时间，算法的复杂度为O((n-m+1)*m)。这种算法没有利用匹配过的信息，每次都从头开始比较，速度很慢。而kmp算法充分利用了之前的匹配信息，从而避免一些明显不合法的位移。加快匹配过程。来看一个例子：

 

#########000xxxx000######                       文本T

|<---- s ---->|000xxxx000~~~                             模式P

 

假设位移为s时，T和P匹配了红色部分的字符，即匹配到了模式P的前10个字符，如果按照传统的匹配方法，下一步就是从位移s+1开始比较，而kmp算法则直接从位移s+7开始比较，而且断定：位移s+7对应的串和模式P的前3个字符是相同的，可

以不用比较，直接从第4个字符开始比较，这种跳跃式的匹配是不是比传统匹配方法快很多，如下图所示：

 

#########000xxxx000######                       文本T

|<-------- s+7-------->| 000xxxx000~~~               模式P

 

 

 

那么kmp是如何实现这种跳跃的呢？注意到红色部分的字符，即模式P的前10个字符，有一个特点：它的开始3个字符和末尾

3个字符是一样的，又已知文本T也存在红色部分的字符，我们把位移移动 10-3 = 7个位置，让模式P的开始3个字符对准文本

T红色部分的末尾3个字符，那么它们的前3个字符必然可以匹配。

二 构造前缀数组

 

上面的例子是文本T和模式P匹配了前面10个字符的情况下发生的，而且我们观察到模式P的前缀P10中，它的开始3个字符和末尾3个字符是一样的。如果对于模式P的所有前缀P1,P2...Pm，都能求出它们首尾有多少个字符是一样的，当然相同的字

符数越多越好，那么就可以按照上面的方法，进行跳跃式的匹配。

 

 

定义：

Pi表示模式P的前i个字符组成的前缀， next[i] = j表示Pi中的开始j个字符和末尾j个字符是一样的，而且对于前缀Pi来说，这样

的j是最大值。next[i] = j的另外一个定义是：有一个含有j个字符的串，它既是Pi的真前缀，又是Pi的真后缀

 

规定：

next[1] = next[0] = 0

 

 

next[i]就是前缀数组，下面通过1个例子来看如何构造前缀数组。

例子1：cacca有5个前缀，求出其对应的next数组。

前缀2为ca，显然首尾没有相同的字符，next[2] = 0

前缀3为cac，显然首尾有共同的字符c，故next[3] = 1

前缀4为cacc，首尾有共同的字符c，故next[4] = 1

前缀5为cacca，首尾有共同的字符ca，故next[5] = 2

 

 

 

如果仔细观察，可以发现构造next[i]的时候，可以利用next[i-1]的结果。假设模式已求得next[10] = 3，如下图所示：

 

 

000#xxx000         前缀P10

000                        末尾3个字符

 

根据前缀函数的定义：next[10] = 3意味着末尾3个字符和P10的前3个字符是一样的

为求next[11]，可以直接比较第4个字符和第11个字符，如下图所示：蓝色和绿色的#号所示，如果它们相等，则

next[11] = next[10]+1 = 4,这是因为next[10] = 3保证了前缀P11和末尾4个字符的前3个字符是一样的.

 

000#xxx000#       前缀P11

000#                      末尾4个字符

 

所以只需验证第4个字符和第11个字符。但如果这两个字符不想等呢？那就继续迭代，利用next[next[10] = next[3]的值来求

next[11]。

【构造next数组】 
void getNext()
{
    int j, k;
    j = 0; k = -1; next[0] = -1;//第j次迭***始之前,k代表next[i-1]的值
    while(j < tlen)
        if(k == -1 || T[j] == T[k])
            next[++j] = ++k;
        else
            k = next[k];


}

三 模拟KMP的查找过程

  和朴素算法的主要区别为，回溯的时候不是回溯到模式串的首位置，而是回溯到模式串的当前的next。


/*
返回模式串T在主串S中首次出现的位置
返回的位置是从0开始的。
*/
//其中tlen为模式串的位置，而slen表示文本串的长度。
int KMP_Index()
{
    int i = 0, j = 0;
    getNext();

    while(i < slen && j < tlen)
    {
        if(j == -1 || S[i] == T[j])
        {
            i++; j++;
        }
        else
            j = next[j];
    }
    if(j == tlen)
        return i - tlen;
    else
        return -1;
}

【算法复杂度】kmp算法在最坏的情况下是O(n+m)的复杂度，这在字符匹配中已经是很好的复杂度！

【优化？】kmp还可以优化吗？当然还有优化，好像是针对next的优化，我还没学，待续！！


【Trick】生活让人越来越浮躁，你是否能静心让学习编程变成你的习惯？There is no reheasal in life,live is everyday!