給出一個(gè)長(zhǎng)字符串text[0...n-1]澈圈，一個(gè)模式字符串pat[0...m-1]耿战，求text中是否存在匹配模式字符串的字串姨蝴，這是常見的字符串匹配的問題堕绩，假設(shè)n > m薄啥。

樸素匹配法

很自然的，我們想到了字符串樸素匹配法逛尚。假設(shè)i，j分別為text刁愿，pat的下標(biāo)绰寞。初始i = 0， j = 0铣口，比較text[i]滤钱，pat[j]，如果相等：i++脑题，j++件缸；否則，j=0叔遂。如果j==m他炊，表示找到了一個(gè)匹配的字串。這種方法的時(shí)間復(fù)雜度是O(m*(n-m+1))已艰。

KMP

1. 算法思想：利用已經(jīng)匹配的信息痊末，減少匹配的次數(shù)，從而減少時(shí)間復(fù)雜度哩掺≡涞總的時(shí)間復(fù)雜度為O(n)。

2. next[]數(shù)組：

旨在表示pat字符串中各位置字符與前綴的匹配長(zhǎng)度嚼吞。如果在比較中盒件，遇到不匹配的字符，不必再令j=0舱禽。如下圖所示：

bg2013050109.png

bg2013050107.png

next[]數(shù)組已經(jīng)知道炒刁，遇到不匹配的情況，我們已經(jīng)知道了前面的匹配呢蔫，如此我們切心，不必令j=0，比較A與“ ”片吊。我們可以令j = next[j-1] = 2绽昏，因?yàn)锳BCDAB已經(jīng)匹配，所以“ABCD”后的“AB”與text相應(yīng)位置已經(jīng)匹配俏脊，有next[j-1]=next[5]=2全谤，我們知道“AB”與pat前綴的“AB”匹配，所以pat前綴"AB"與text[i-1]和text[i-2]匹配爷贫，那么我們直接令j=2认然，比較后續(xù)的字符串就可以了补憾。

如何求next[]數(shù)組？
（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; // 前綴長(zhǎng)度
        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ìn)行匹配

上文已經(jīng)說過盈匾，當(dāng)遇到不匹配的字符時(shí)，如果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;
            }
        }
    }