algorithm
クヌースモリスプラット(KMP)アルゴリズム
サーチ…
前書き
KMPは、不一致が生じたときに、次の一致がどこで始まるかを決定するのに十分な情報を有するという観察を利用して、主な「文字列」 S内の「単語」 Wの出現を検索するパターンマッチングアルゴリズムである。この情報を利用して、われわれが知っている文字と一致することを避けてください。パターンを検索するための最悪の複雑さは、 O(n)に減少します。
KMP-例
アルゴリズム
このアルゴリズムは2段階の処理です。最初に補助配列lps []を作成し、この配列を使用してパターンを検索します。
前処理 :
- パターンを前処理し、一致する文字をスキップするために使用される補助配列lps []を作成します。
- ここで、lps []は接尾辞でもある最長の正しい接頭辞を示します。適切な接頭辞は、文字列全体が含まれない接頭辞です。たとえば、 ABCの接頭辞は"" 、 "A" 、 "AB" 、 "ABC"です。適切なプレフィックスは"" 、 "A" 、 "AB"です。文字列の接尾辞は"" 、 "C" 、 "BC" 、 "ABC"です。
検索
私たちは、[J] [i]とパット TXTマッチング文字を維持し、 パット[J]とtxtの[i]はマッチングを維持しながら、iとjをインクリメント保ちます。
不一致を見ると、文字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;
}
}
Modified text is an extract of the original Stack Overflow Documentation
ライセンスを受けた CC BY-SA 3.0
所属していない Stack Overflow