algorithm
クヌースモリスプラット（KMP）アルゴリズム

前書き

KMP-例

アルゴリズム

このアルゴリズムは2段階の処理です。最初に補助配列lps []を作成し、この配列を使用してパターンを検索します。

前処理 ：

1. パターンを前処理し、一致する文字をスキップするために使用される補助配列lps []を作成します。
2. ここで、lps []は接尾辞でもある最長の正しい接頭辞を示します。適切な接頭辞は、文字列全体が含まれない接頭辞です。たとえば、 ABCの接頭辞は"" 、 "A" 、 "AB" 、 "ABC"です。適切なプレフィックスは"" 、 "A" 、 "AB"です。文字列の接尾辞は"" 、 "C" 、 "BC" 、 "ABC"です。

検索

1. 私たちは、[J] [i]とパット TXTマッチング文字を維持し、 パット[J]とtxtの[i]はマッチングを維持しながら、iとjをインクリメント保ちます。

2. 不一致を見ると、文字pat [0..j-1]がtxt [i-j + 1 ... i-1]と一致することがわかります。また、lps [j-1]はpatの文字数[0 ... J-1]、適切な接頭辞とsuffix.Fromの両方が、この私たちはこれらのLPS TXTと[J-1]の文字と一致する必要がないことを結論付けることができます[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;
    }

}