模式匹配KMP算法

关于KMP算法的原理网上有很详细的解释，我试着总结理解一下：

KMP算法是什么

　　以这张图片为例子

　　匹配到j=5时失效了，BF算法里我们会使i=1，j=0，再看s的第i位开始能不能匹配，而KMP算法接下来就去比较T[2]（next[5]=2）和S[5]

next数组什么意思？

就是当t[i]不匹配时,就让i=next[i]再去比较，则t[next[i]]前面的部分和s[j]前面一定是相同的，因为t[next[i]]前面的部分和t[i]前面的部分是相同的，图中相同颜色代表字符串相同部分。也就是我们利用模式串的自身匹配的特点，来减少和目标串的比较。

next数组怎么算？

我们算好next[i]，去算next[i+1]时分两种情况：

T[i]==T[k] （k=next[i]）时，next[i+1]=k+1。

T[i]!=T[k] 时，先看图左，在匹配的部分里（灰色）有更小的一段（蓝色），是next[next[i]]前面的子串，根据next数组的含义，蓝色的和粉色的子串相同，因为两段灰色是相同的，那左蓝就和右粉相同，

如果这时T_i=T_next[k]，那next[i+1]就是next[k]+1，否则继续找更小的一段，直到k=-1，那么next[i]=0。

void get_next(const string &T,int *next){

    int i=,k=-;

    next[i]=k;

    while(T[i]){

        if(k==-||T[k]==T[i])

        {

            ++k;

            ++i;

            next[i]=k;

        }else{

            k=next[k];

        }

    }

}

但是其实还可以再改进

　　上面算next[i+1]时不考虑T[i+1]是什么，T[i]失配，用T[next[i]]去比较，可以保证T[next[i]]前面的都能匹配，但是如果T[next[i]]==T[i]，跳到next[i]肯定还是失配，所以算next时要考虑一下T[next[i]]和T[i]是否相等。

算好next[i]，去算next[i+1]时：

　　　如果 T[k]==T[i]且T[i+1]==T[k+1]，由于T[i+1]失配了，T[k+1]肯定也会失配，那next[i+1]应该继续跳到next[k+1]。

改进后的next计算代码：

void get_next()

{

    int i=,k=-;

    next[i]=k;

    while(T[i])

    {

        if(k==-||T[i]==T[k])

        {

            ++k;

            ++i;

            if(T[i] == T[k])

                next[i] = next[k];

            else

                next[i] = k;

        }

        else

            k=next[k];

    }

}

另一种get_next的写法

void get_next()

{

    int i,k=-;

    next[]=k;

    for(i=;T[i];i++){

        while(k>= && T[k+]!=T[i]) k=next[k];

        if (T[k+]==T[i]) k++;

        next[i]=k;

    }

}

完整程序代码：

#include<iostream>

#include<cstring>

const int N = ;

int next[N];

char T[N],S[N];

void get_next()

{

    int i=,k=-;

    next[i]=k;

    while(T[i]){

        if(k==-||T[i]==T[k]){

            ++i;

            ++k;

            if(T[i]==T[k])

                next[i]=next[k];

            else

                next[i]=k;

        }else{

            k=next[k];

        }

    }

}

int KMP()

{

    int i=,j=;

    while(S[j]&&(i==-||T[i])){

        if(i==-||S[j]==T[i]){

            ++i;

            ++j;

        }else{

            i=next[i];

        }

    }

    if(!T[i])return j-i;

    return -;

}

int main(){

    std::cin>>T>>S;

    get_next();

    std::cout<<KMP()+<<std::endl;

    return ;

}

/*

abcaccdacb

abcaccdaccccaccabcaccdaccacabcaccdacb

输出28

*/

巴特西