Knuth-Morris-Pratt algorithm

2018/08/14 ALGO

In computer science, the Knuth–Morris–Pratt string-searching algorithm (or KMP algorithm) searches for occurrences of a “word” W within a main “text string” S by employing the observation that when a mismatch occurs, the word itself embodies sufficient information to determine where the next match could begin, thus bypassing re-examination of previously matched characters.

子字符串查找

字符串的一种基本操作是子字符串查找。在C++中的string库中有子字符串查找函数:

string str = "Thank you for your smile.";
string str2 = "you";
string str3 = "me";
if(str.find(str2) != string::npos)
    cout << str.find(str2);
if(str.find(str2, 7) != string::npos)
    cout << str.find(str2, 7);
if(str.find(str3) != string::npos)
    cout << str.find(str3) << endl;
else
    cout << "not" << endl;

str.find(str2),当str2是str的字串时,返回其在str中第一次出现的位置。否则返回string::npos。上面的代码输出结果是 [614not] 。

当你在文本编辑器或是浏览器中查找某个单词时,就是在查找子字符串。字符串查找的另外一个经典应用是在截获的通信内容中寻找某种重要的模式。一位军队将领感兴趣的可能是在截获的文本中寻找和“拂晓进攻”类似的语句。一名黑客感兴趣的可能是在内存中查找与“password:”相关的内容。在现在,我们经常使用搜索引擎在互联网海量信息中查找字符串。

约定

往下阅读之前,我们约定两个名词:

  • 文本字符串:原字符串,用txt表示。
  • 模式字符串:子字符串,用pat表示。

例如在A串中查找B串,那么A串是文本字符串,B串是模式字符串。同时,我们使用循环变量i来表示文本字符串的第i个字符,使用循环变量j来表示模式字符串的第j个字符。

暴力子字符串查找算法

暴力搜索的思路很简单,那就是使用两个位置指针i和j分别判断文本与模式位直到长度结束或者找到模式为止。下面是暴力方法的java代码:

public static int search(String pat, String txt){
    int M = pat.length();
    int N = txt.length();
    for(int i=0;i<=N-M;i++){
        int j;
        for(j=0;j<M;j++){
            if(txt.charAt(i+j) != pat.charAt(j)){
                break;
            }
        }
        if(j == M){
            return i;
        }
    }
}

指针i从txt的位置0开始移动到N-M位置,指针j则判断pat的字符是否与指针i+j指向的字符一致。如果一致,则指针j向下一个字符位置移动,否则重新再来。通过上面的代码不难得出,暴力的复杂度是O(NM)。但是在典型的字符串处理程序中,NM这种最坏情况是极少出现的。因为绝大多时候,指针j都是不移动的,此时txt与pat的第一个字符已经是不匹配,指针i向下一个字符位置移动,而指针j归零。由此暴力搜索算法看起来也并不是很糟糕,大部分情况下是近似线性时间。

Deterministic Finite Automaton

In the theory of computation, a branch of theoretical computer science, a deterministic finite automaton (DFA) also known as deterministic finite acceptor (DFA), deterministic finite state machine (DFSM), or deterministic finite state automaton (DFSA) is a finite-state machine that accepts or rejects strings of symbols and only produces a unique computation (or run) of the automaton for each input string.

在计算理论(编译原理课程)中,有限状态自动机是对于一个属于自动机状态和该自动机字母表的字符,能够根据事先给定的转移函数转移到下一个状态。

关于DFA的细节,可以参考《编译原理》或者是《计算理论》,这里不多做阐述。下面以一个例子简单描述DFA:

在这个DFA中,有限的状态集合Q包括{S0、S1、S2};输入字母表是{0、1};有6条转移函数,上图的表格呈现;开始状态为S0,结束状态为S2。开始状态的特点是,这个圈圈有一个不带任何状态的箭头指向自己,而结束状态的特点是一个同心环。我们来分析这个DFA能够识别什么模式?

从S0开始,如果输入0,那么状态转移到S1,再输入1,状态转移到S2。因此这个DFA能够识别01串。同时我们发现S1状态如果输入0又会回到自己本身,因此001、0001、0…01也可以被这个DFA识别。通过发现规律,这个DFA能够识别01、001、0001、0…01等串。

对DFA有初步认识后,那么子字符串搜索问题,其实可以理解为将模式字符串生成一个DFA,然后从开始状态逐个输入文本字符串,如果某一时刻到达结束状态,那么我们就说找到了匹配的字符串,也就是DFA匹配这个模式。例如下图中,对模式字符串ABABAC的构造:

这个图片中的描绘并不规范。特别说明,有限状态集合Q={0,1,2,3,4,5,6};字母表{A,B,C};其中0号节点是开始状态,6号节点是结束状态。

构造DFA

结合上述关于DFA的描述,那么要如何创建DFA呢。下面使用dfa[k][j]来表达模式字符串的第j个字符遇到字母表第k个元素时转换的状态。例如下图:

例如,dfa[2][5]=6,表示从状态5输入字母C(字母C对应k=2)时转换到状态6。dfa数组中有几个规律,首先每列依次有唯一的j+1的状态,因为每个状态j都有唯一一个转换方程到下一个状态j+1。然后,第一列包含开始状态,最后一列包含结束状态。

那么应该如何生成这个二维数组呢?首先第1列,也就是dfa[][0],初始化为全0,将dfa[pat.charAt(0)][0]赋值为1。原因是状态0遇到pat的首位字母会进入状态1,其余的字母都会转换到状态0本身。紧接着的第i列,克隆前面的某X列,然后将dfa[pat.charAt(j)][j]赋值为j+1。

那问题又转换到“X是怎么求出来的”。《算法 4th》中提到,X=dfa[pat.charAt(j)][X]。这个公式为什么是这么来的,课本中并没有提及。下面是原文:

The final crucial detail to the computation is to observe that maintaining the restart position X when working on column j of dfa[][] is easy because X < j so that we can use the partially built DFA to do the job—the next value of X is dfa[pat.charAt(j)][X]). Continuing our example from the previous paragraph, we would update the value of X to dfa[‘C’][3] = 0 (but we do not use that value because the DFA construction is complete).

因此我们得到这样一段求解DFA的代码:

dfa[pat.charAt(0)][0] = 1;
for(int X=0,j=1;j<M;j++){
    for(int c=0;c<R;c++){
        dfa[c][j] = dfa[c][X];
    }
    dfa[pat.charAt(j)][j] = j+1;
    X = dfa[pat.charAt(j)][X];
}

上面的循环分为3个步骤:

  1. 将dfa[][X]复制到dfa[][j]。
  2. 将dfa[pat.charAt(j)][j]赋值为j+1。
  3. 更新X。

至于步骤3,更新X的原理是什么,我目前也没有找到很好的解释。一个参考的说法是,X是DFA在迭代的过程中依靠不完整的信息得出新的回退状态的位置。这个解释不够直观,也不够简洁。至于为什么X的求解公式是X=dfa[pat.charAt(j)][X],《算法》书本中没有给出解释,我也不得其解,这里留下一个疑问。

KMP

综合上面所述,求出dfa数组之后,就可以进行KMP的搜索了。每次检查当前txt的字符抵达什么状态,如果到达终点状态,就表明找到子字符串了。

public class KMP{
    private String pat;
    private int[][] dfa;

    public KMP(String pat){
        this.pat = pat;
        int M = pat.length();
        int R = 256;
        dfa = new int[R][M];
        dfa[pat.charAt(0)][0] = 1;
        for(int X=0,j=1;j<M;j++){
            for(int c=0;c<R;c++){
                dfa[c][j] = dfa[c][X];
            }
            dfa[pat.charAt(j)][j] = j+1;
            X = dfa[pat.charAt(j)][X];
        }
    }

    public int search(String txt){
        int i, j, N = txt.length(), M = pat.length();
        for(i=0,j=0;i<N && j<M;i++){
            j=dfa[txt.charAt(i)][j];
        }
        if(j==M){
            return i-M;
        } else {
            return N;
        }
    }
}

KMP的算法复杂度是O(M+N),最坏情况下提供一个线性级别的运行时间。

KMP的C实现

上面的实现中使用了dfa二维数组,有更好的实现方式。这部分内容的详细解析等后续补充。

void kmp_pre(char x[], int m, int next[]){
    int i, j;
    j = next[0] = -1;
    i = 0;
    while(i<m){
        while(-1!=j && x[i] != x[j]){
            j = next[j];
        }
        next[++i] = ++j;
    }
}

void preKMP(char x[], int m, int kmpNext[]){
    int i, j;
    j = kmpNext[0] = -1;
    i = 0;
    while(i<m){
        while(-1!=j && x[i] != x[j]){
            j = kmpNext[j];
        }
        if(x[++i] == x[++j]){
            kmpNext[i] = kmpNext[j];
        } else {
            kmpNext[i] = j;
        }
    }
}

int next[10010];
int KMP_Count(char x[], int m, char y[], int n){
    int i, j;
    int ans = 0;
    kmp_pre(x, m, next);
    // preKMP(x, m, next);
    i = j = 0;
    while(i<n){
        while(-1!=j && y[i]!=x[j]){
            j=next[j];
        }
        i++;
        j++;
        if(j>=m){
            ans++;
            j = next[j];
        }
    }
    return ans;
}

Search

    Table of Contents