KMP初步

本人刚学KMP，望大佬指出说法不合适的地方......

 

KMP这个算法主要可以用来解决求字符串中子串的位置（当然不止这一点），绝对不是字面上的那个什么意思......它是个算法！算法！全称Knuth-Morris-Pratt！

对了，有人会问：既然求子串，那为什么不用c++库里自带的 strstr(str1，str2) 函数呢？ 告诉你，那东西是暴力！用暴力求的！大数据过不了！

所以我们才要KMP......

例题：

题目描述

给出两个字符串s1和s2，其中s2为s1的子串，求出s2在s1中所有出现的位置。

输入输出格式

输入格式：

第一行为一个字符串，即为s1

第二行为一个字符串，即为s2

 

输出格式：

若干行，每行包含一个整数，表示s2在s1中出现的位置

输入输出样例

输入样例

ABABABC
ABA

输出样例

0
2

 

先令 s1 长度为 n ， s2 长度为 m 。KMP的算法就是先用 O(m) 的时间对 s2 进行预处理，再用 O(n) 的时间完成匹配。

它和朴素的算法的区别就是：若 s1[i] != s2[j] 那么朴素算法会从 s2 的头开始匹配；而KMP会从已有的最长的 s2 的部分开始匹配。

举个例子：s2 = abbaaba，当 s1[i] 和 s2[6] ('a') 比较时，若 s1[i] != s2[5] 朴素的算法就是回到 s2 的头重新比较，而 KMP 可以利用 s2 本身的特性判断出 再和 s2[3] ('b') 比较是有可能匹配的。画一个图，可能会直观些。以下是一个状态转移图，每一个圈代表一个状态，箭头下的字母代表该状态读到这个字母而转变成下一个状态。

 

从这个图就可以看出，若状态6的下一个不是 'a' 的话，就会到状态2,。换句话说，就是到状态6的这个串应该回到和它的最长后缀相等的 s2 的前缀，也就是这里的从状态4开始的 "ab"，和从状态0开始的 "ab"。

所以对于每一个状态，要么是匹配对了进入下一个状态，要么不对（失配）返回以前的某个状态。对于失配状态，我们只需用一个一位数组 f[m] 来储存，则 f[i] 表示状态 i 失配时应转移到的状态，特别注意 f[0] = 0。

有了这个失配函数后，KMP的代码就可以写出来了：

void kmp(char t[], char p[], int f[])
{
    int n = strlen(t), m = strlen(p);
    getfail(p, f, m);    //构造失配函数 
    int j = 0;            //代表当前状态编号，初始为0 
    for(int i = 0; i < n; ++i)
    {
        while(j && t[i] != p[j]) j = f[j];    //按失配边走，直到可以匹配 
        if(p[j] == t[i]) j++;    //因为可能回到头，所以还要判断一下 
        if(j == m) printf("%d
", i - m + 2);    //匹配成功，输出匹配点位置 
    }
}

接下来就是就要构造失配函数，即状态转移图，这是构造KMP算法的关键。思想是”用自己匹配自己“，根据 f[0], f[1] ...... 递推 f[i]。

还是放图更直观些

假如到状态<2> 的失配函数是<1>，那么必定有<1> == <2>，此时再进入下一个状态 i，若<1> 的下一个状态 j == i，那么 i 失配时就一定转移到状态 j ；若 i != j，再找 j 失配时应转移到的状态 k ，在比较 i 和 k。相等时，i 失配就转移到 k，否则继续找，直到转移到0，此时 i 失配时就回到初始状态了。

代码

void getfail(char p[], int f[], int m)
{
    f[0] = 0; f[1] = 0;        //递推边界初值 
    for(int i = 1; i < m; ++i)
    {
        int j = f[i];
        while(j && p[j] != p[i]) j = f[j];
        f[i + 1] = p[j] == p[i] ? j + 1: 0;
         //若没回到初始状态，那么 i + 1状态就转移到 j + 1 
    }
    return;
}

这就是KMP的板子了，要想真正学好KMP，一定要将这个失配函数怎样构造的理解透彻，最好别死记硬背板子。