KMP-實施例

演算法

這個演算法是一個兩步過程。首先我們建立一個輔助陣列 lps []然後使用這個陣列來搜尋模式。

預處理 ：

1. 我們預處理模式並建立一個輔助陣列 lps []，用於在匹配時跳過字元。
2. 這裡 lps []表示最長的正確字首，也是字尾。正確的字首是不包括整個字串的字首。例如，字串 ABC 的字首是 “” ， A ， AB 和 ABC 。正確的字首是 “” ， A 和 AB 。字串的字尾是 “” ， C ， BC 和 ABC 。

搜尋

1. 我們保持匹配字元 txt [i] 和 pat [j] 並保持遞增 i 和 j，同時 pat [j] 和 txt [i] 保持匹配。

2. 當我們看到不匹配時，我們知道字元 pat [0..j-1] 與 txt [i-j + 1 … i-1] 匹配。我們也知道 lps [j-1]是 pat 的字元數 [0 … j-1] 既是正確的字首又是字尾。由此我們可以得出結論，我們不需要將這些 lps [j-1] 字元與 txt [ij … i-1] 匹配，因為我們知道這些字元無論如何都會匹配。

在 Java 中實現

public class KMP {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        String str = "abcabdabc";
        String pattern = "abc";
        KMP obj = new KMP();
        System.out.println(obj.patternExistKMP(str.toCharArray(), pattern.toCharArray()));
    }
    
    public int[] computeLPS(char[] str){
        int lps[] = new int[str.length];
        
        lps[0] = 0;
        int j = 0;
        for(int i =1;i<str.length;i++){
            if(str[j] == str[i]){
                lps[i] = j+1;
                j++;
                i++;
            }else{
                if(j!=0){
                    j = lps[j-1];
                }else{
                    lps[i] = j+1;
                    i++;
                }
            }
            
        }
        
        return lps;
    }
    
    public boolean patternExistKMP(char[] text,char[] pat){
        int[] lps = computeLPS(pat);
        int i=0,j=0;
        while(i<text.length && j<pat.length){
            if(text[i] == pat[j]){
                i++;
                j++;
            }else{
                if(j!=0){
                    j = lps[j-1];
                }else{
                    i++;
                }
            }
        }
        
        if(j==pat.length)
            return true;
        return false;
    }

}