kmp算法详解

模式匹配问题

　　模式匹配问题是指，给出一个主串s和子串t，要求在s中寻找子串t，求出t出现的第一个位置，t又称为模式串。

BF算法

　　考虑最暴力的做法，我们设i为s的下标，j为t的下标。

　　从s[0]和t[0]开始匹配，若匹配成功则i++，j++匹配下一个。

　　若匹配不成功，即s[i] != t[j]，则令i =i-j+1，j=0。相当于每次失配时j移动到模式串开头，i移动到本次失配的起始字符的下一个位置。

int bf(char *s,char *t){//主串s，子串t进行模式匹配，返回第一次出现子串t的开始下标 
    int i=0,j=0;
    while(s[i]!=''&&t[j]!=''){
        if(s[i]==t[j]){
            i++;
            j++;
        }
        else{
            i=i-j+1;
            j=0;
        }
    }
    if(t[j]=='') return (i-j);//返回起始下标 
    else return -1;//标明j没有走到t的尾巴，主串s不含子串t 
}

　　例如主串为ababcd，子串为abc，我们来模拟一遍BF算法。

　　i=0，j=0时s[i]=t[j]，令i++=1，j++=1

　　i=1，j=1时s[i]=t[j]，令i++=2，j++=2

　　i=2，j=2时s[i]!=t[j]，令i=1，j=0

　　i=1，j=0时s[i]!=t[j]，令i=2，j=0

　　i=2，j=0时s[i]=t[j]，令i++=3，j++=1

　　i=3，j=1时s[i]=t[j]，令i++=4，j++=2

　　i=4，j=2时s[i]=t[j]，令i++=5，j++=3，此时退出循环

　　判定t[j]==''，故返回5-3=2。

　　我们可以很容易知道，BF算法最坏情况下要比较lens*lent次，故时间复杂度为O(nm)，量级过大。

kmp算法

　　BF算法时间复杂度高是因为每次失配时，j指针都要移动到0位置，i都要回溯，然后从模式串初始位置一个一个匹配。

　　那么如果在失配时，j不移动到初始位置，i也不进行回溯，就可以优化BF算法了，kmp算法就是这个思路，对于模式串，有一个next数组，next[j]表示j位置失配时，j的下一个位置。

　　现在先不考虑next数组怎么求，若已知next数组，我们可以写出如下匹配代码，其中大部分代码和BF算法类似，只有j==-1和失配时j变成next[j]不同。

int kmp(string s,string t,int sta){
    int i=sta,j=0;
    int len1=s.length(),len2=t.length();
    while(i<len1&&j<len2){
        if(j==-1||s[i]==t[j]){
            i++;
            j++;
        }
        else
            j=nxt[j];
    }
    if(j==len2) return (i-j);
    else return -1; 
}

　　为了理解next数组我们先要学一个名词——最长公共前后缀，假设有一个串P=“p₀p₁p₂ …p_j-1p_j”。如果存在p₀p₁…p_k-1p_k = p_j-_kp_j-k+1…p_j-1p_j，我们就说在P串中有一个最大长度为k+1的公共前后缀。手动找最长公共前后缀的方法是把所有前缀和后缀写出来，看匹配的哪个最长。

　　这样对于字符串P的每一个位置都可以求出它的最长公共前后缀，这个表的含义是当前字符作为最后一个字符的子串的最长公共前后缀。

　　next数组的定义是，对于每个位置，next是起始字符到当前字符的前一个字符的子串的最长公共前后缀，相当与对上一个表进行右移，第一个位置无实际含义我们赋值为-1。

　　这是我们手动算出来的next数组，next[j]的本质就是0,1,2...j-1这段字符串的最长公共前后缀。

　　那么怎么用代码推next数组呢？

　　我们很容易知道，next[0]=-1，next[1]=0，考虑j>1，已知next[j]=k如何求next[j+1]。

分两种情况：

　　1.当t[j]=t[k]时，next[j]=next[j+1]=k+1，代表在j+1前的字符有k+1个最长公共前后缀，下图以字符E举例

　　2.当t[j]=t[k]时，这说明p₀p₁…p_k-1p_k != p_j-kp_j-k+1…p_j-1p_j，这时我们试图寻找比k短的公共前后缀，我们递归令k=next[k]，试图使p₀p₁…p_k’-1p_k’ = p_j-k’p_j-k’+1…p_j-1p_j则next[j+1] = k’+1，否则next[j+1]=0。

　　综上我们可以写出如下求next数组的代码：

void getnext(string t){
    int j=0,k=-1;
    nxt[j]=k;
    int len=t.length();
    while(j<len){
        if(k==-1||t[j]==t[k]){
            j++;
            k++;
            if(t[j]!=t[k])
                nxt[j]=k;
            else
                nxt[j]=nxt[k];
        }
        else k=nxt[k];
    }
}

模板

int kmp(string s,string t,int sta){
    int i=sta,j=0;
    int len1=s.length(),len2=t.length();
    while(i<len1&&j<len2){
        if(j==-1||s[i]==t[j]){
            i++;
            j++;
        }
        else
            j=nxt[j];
    }
    if(j==len2) return (i-j);
    else return -1; 
}
void getnext(string t){
    int j=0,k=-1;
    nxt[j]=k;
    int len=t.length();
    while(j<len){
        if(k==-1||t[j]==t[k]){
            j++;
            k++;
            if(t[j]!=t[k])
                nxt[j]=k;
            else
                nxt[j]=nxt[k];
        }
        else k=nxt[k];
    }
}

View Code