KMP算法详写

前言：今天上数据结构的课后想到之前学这个算法的时候并没有写一个详细的博客，现在补一个，也算是加深印象。

串模式匹配算法

子串的定位运算通常称为串的模式匹配或串匹配。此算法的应用非常广泛，比如在 搜索引擎拼写检查，语言翻译，数据压缩等应用中，都需要进行传匹配
串的模式匹配设有两个字符串S和T，设S位主串，也称正文串；设T为子串，也称为模式在子串中查找与模式T相匹配的子串，如果匹配成功，确定相匹配的子串中的第一个字符串S中出现的位置。
著名的模式匹配算法有BF算法和KMP算法，下面详细介绍两种算法。

1.BF算法

BF(Brute Force)算法是普通的模式匹配算法，BF算法的思想就是将目标串S的第一个字符与模式串T的第一个字符进行匹配，若相等，则继续比较S的第二个字符和 T的第二个字符；若不相等，则比较S的第二个字符和T的第一个字符，依次比较下去，直到得出最后的匹配结果。
比如

int BF(char S[],char T[],int pos)
{
   //c从第pos位开始搜索匹配
    int i=pos,j=0;
    while(S[i+j]!='\0'&&T[j]!='\0')
    {
   
        if(S[i+j]==T[j])
            j++;
        else
        {
   
            i++;
            j=0;
        }
    }
    if(T[j]=='\0')//返回的是匹配找到的开始位置
        return i+1;
    else
        return -1;
}

BF算法比较直接，是一种蛮力算法，该算法最坏情况下要进行M*(N-M+1)次比较，时间复杂度为O(M*N)。

这个算法的话时间复杂度高。

那么对于有需要效率非常高的时候。我们就需要使用效率非常高的字符串匹配算法，即KMP算法。

KMP算法

这个改进算法是由Knuth ，Morris和 Pratt 同时设计实现的，因此简称为KMP。
这个算法是在BF算法上改进的，那么我们先来了解一下它是怎么改进的。

每当一趟匹配过程中出现字符比较不相等时，不需要回溯i指针，而是利用已经得到的"部分匹配"的结果将模式向右"滑动"尽可能远的一段距离后，继续进行比较。
举个例子：
第一躺 ： ababcabcacbab
： abc
第二趟：ababcabcacbab
： abc
第三趟 ：ababcabcacbab
： abc
或者看动态图

通过这个图行我们可以理解了改进 后是怎么比较的，那么知道原理后，我们需要去实现KMP算法。下面就是开始实现：

我们先得到next[]，然后实现KMP算法。

void get_next(string t,int next[])//
{
   
    int len=t.length();
    i=1;
    nex[1]=0;
    j=0;
    while(i<len)
    {
   
        if(j==0||t[i]==t[j])
        {
   
            ++i,++j;
            next[i]=j;
        }
        else
            j=next[j];
    }
}

int KMP(string s,string t,int pos)
{
   
    i=pos,j=1;
    while(i<=s[0]&&j<=t[0])
    {
   
        if(j==0||s[i]==s[j])
        {
   
            ++i;++j;
        }
        else
            j=next[j];
    }
    if(j>t[0])
    {
   
        return i-t[0];
    }
    else
        return 0;
}