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;
    }

}