algorithm
크 누스 모리스 프랫 (KMP) 알고리즘

소개

KMP- 예

연산

이 알고리즘은 두 단계 과정입니다. 먼저 보조 배열 lps []를 만든 다음이 배열을 사용하여 패턴을 검색합니다.

전처리 :

1. 패턴을 사전 처리하고 일치하는 문자를 건너 뛰는 데 사용되는 보조 배열 lps []를 만듭니다.
2. 여기서 lps []는 접미어 인 가장 긴 적절한 접두사를 나타냅니다. 올바른 접두어는 전체 문자열이 포함되지 않은 접두사입니다. 예를 들어, 문자열 ABC의 접두사는 "" , "A" , "AB" 및 "ABC" 입니다. 적절한 접두사는 "" , "A" 및 "AB" 입니다. 문자열의 접미사는 "" , "C" , "BC" 및 "ABC" 입니다.

수색

1. pat [j] 와 txt [i] 가 일치하는 동안 txt [i] 와 pat [j]의 일치하는 문자를 유지하고 i와 j를 계속 증가시킵니다.

2. 우리는 불일치를 볼 때, 우리는 문자 팻 [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;
    }

}