algorithm
크 누스 모리스 프랫 (KMP) 알고리즘
수색…
소개
KMP는 불일치가 발생하면 다음 일치 항목을 시작할 위치를 결정할 수있는 충분한 정보를 가지고 있다는 관찰을 사용하여 주 "텍스트 문자열" S 내의 "단어" W의 발생을 검색하는 패턴 일치 알고리즘입니다. 이 정보를 이용하여 우리가 알 수있는 문자를 매치시키는 것을 피하십시오. 패턴 검색을위한 최악의 경우의 복잡성은 O (n)로 감소합니다.
KMP- 예
연산
이 알고리즘은 두 단계 과정입니다. 먼저 보조 배열 lps []를 만든 다음이 배열을 사용하여 패턴을 검색합니다.
전처리 :
- 패턴을 사전 처리하고 일치하는 문자를 건너 뛰는 데 사용되는 보조 배열 lps []를 만듭니다.
- 여기서 lps []는 접미어 인 가장 긴 적절한 접두사를 나타냅니다. 올바른 접두어는 전체 문자열이 포함되지 않은 접두사입니다. 예를 들어, 문자열 ABC의 접두사는 "" , "A" , "AB" 및 "ABC" 입니다. 적절한 접두사는 "" , "A" 및 "AB" 입니다. 문자열의 접미사는 "" , "C" , "BC" 및 "ABC" 입니다.
수색
pat [j] 와 txt [i] 가 일치하는 동안 txt [i] 와 pat [j]의 일치하는 문자를 유지하고 i와 j를 계속 증가시킵니다.
우리는 불일치를 볼 때, 우리는 문자 팻 [0..j-1] TXT와 일치 [I-J + 1 ... 난-1] 먹 또한 LPS [J-1] 팻 문자의 수가 것을 알고 알고 [0 ... J-1] 적절한 접두사와 suffix.From 모두이 우리가이 LPS TXT와 [J-1] 문자와 일치 할 필요가 없다는 결론을 내릴 수있다 [IJ ... I-1] 우리는 이러한 문자 것을 알고 있기 때문에 어쨌든 일치 할 것입니다.
자바 구현
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