KMP

给出一个长字符串text[0...n-1]，一个模式字符串pat[0...m-1]，求text中是否存在匹配模式字符串的字串，这是常见的字符串匹配的问题，假设n > m。

朴素匹配法

---

很自然的，我们想到了字符串朴素匹配法。假设i，j分别为text，pat的下标。初始i = 0， j = 0，比较text[i]，pat[j]，如果相等：i++，j++；否则，j=0。如果j==m，表示找到了一个匹配的字串。这种方法的时间复杂度是O(m*(n-m+1))。

KMP

---

1. 算法思想：利用已经匹配的信息，减少匹配的次数，从而减少时间复杂度。总的时间复杂度为O(n)。

2. next[]数组：

旨在表示pat字符串中各位置字符与前缀的匹配长度。如果在比较中，遇到不匹配的字符，不必再令j=0。如下图所示：

bg2013050109.png bg2013050107.png

next[]数组已经知道，遇到不匹配的情况，我们已经知道了前面的匹配，如此我们，不必令j=0，比较A与“ ”。我们可以令j = next[j-1] = 2，因为ABCDAB已经匹配，所以“ABCD”后的“AB”与text相应位置已经匹配，有next[j-1]=next[5]=2，我们知道“AB”与pat前缀的“AB”匹配，所以pat前缀"AB"与text[i-1]和text[i-2]匹配，那么我们直接令j=2，比较后续的字符串就可以了。

如何求next[]数组？
（1）初始next[0] = 0
（2）if (pat[j] = pat[next[j-1]])，next[j] = next[j-1] + 1
else {
if (next[j-1] != 0) {
比较pat[j]与pat[next[next[j] - 1]];
}
else {
next[j] = 0;
}
}

代码如下：

public void computeNext(String pat, int[] next) {
        int m = pat.length();
        int len = 0; // 前缀长度
        int i = 1;
        int[] next = new int[m];
        next[0] = 0;
        while (i < m) {
                 if (pat.charAt(i) == pat.charAt(len)) {
                          len++;
                          next[i] = len;
                          i++;
                 }
                  else {
                           if (len != 0) {
                                    len = next[len-1];
                           }
                           else {
                                    next[i] = 0;
                                    i++;
                           }
                 }
        }
}

3. 利用next[]进行匹配

上文已经说过，当遇到不匹配的字符时，如果j！=0，令j = next[j-1]即可；如果j == 0， i = i + 1;

public void KMPSearch(String pat, String txt)
    {
        int M = pat.length();
        int N = txt.length();
 
        // create lps[] that will hold the longest
        // prefix suffix values for pattern
        int lps[] = new int[M];
        int j = 0;  // index for pat[]
 
        // Preprocess the pattern (calculate lps[]
        // array)
        computeLPSArray(pat,M,lps);
 
        int i = 0;  // index for txt[]
        while (i < N)
        {
            if (pat.charAt(j) == txt.charAt(i))
            {
                j++;
                i++;
            }
            if (j == M)
            {
                System.out.println("Found pattern "+
                              "at index " + (i-j));
                j = lps[j-1];
            }
 
            // mismatch after j matches
            else if (i < N && pat.charAt(j) != txt.charAt(i))
            {
                // Do not match lps[0..lps[j-1]] characters,
                // they will match anyway
                if (j != 0)
                    j = lps[j-1];
                else
                    i = i+1;
            }
        }
    }