KMP 알고리즘

알고리즘 소개

 

KMP 알고리즘은 특정 문자열에서 특정 문자열의 패턴이 존재하는가를 판단할때 유용하다.

 

ex) "AAABCCDEFSDFSWESSSAAWWSSW" 문자열에서 ABC 문자열이 존재하는지를 찾기 위해서는  일반적으로 찾기위해서 N*M 번 모든경우를 뒤저야한다. 하지만 KMP 알고리즘을 사용한다면 훨씬 빠르게 pattern을  찾을 수 있다.

 

여기서는 접미사와 접두사의 개념을 이해해야한다.

 

접두사 : 문자열의 앞쪽

 

접미사 : 문자열의 끝쪽

 

즉 찾을 문자열의 접두사와 접미사의 비교를 통해 반복적으로 일어나는 문자열의 길이와 위치를 알수 있으면

실제 문자열에서 찾을때 처음부터 다시 찾는것이아니라 반복적으로 일어난 패턴에대해서는 이미 같을 것이니깐 

거기서부터찾는 것이다.

 

ex)

ABDABC 라는 무자열 이있다. 만약 어떤 문자열에서 이문자열의 존재여부를 찾는데 

 

마지막 6번째 C를 비교할때 이문자값이랑 실제값이랑 틀리다면 ABDABC 문자열을 A처음부터 비교해 나가야할까??

아니다 ABDAB 까지는 똑같이 맞앗다는 소리니 두번째 B로 되돌아간후 D와 현재 비교하는 문자열을 비교해주면된다.

 

이제 방법도 알았으니 Pi 이러한 문자의 위치를 저장하는 Pi 배열을 만들어보자.

 

길이가 1~N 까지 문자열을 생각하면서 접미사 접두사가 같을때 위치를 저장해보겠다

 

길이가 1일때 Pi[0] = 0 이다. 이때 j값은 현재 비교하면서 이까지 일치한다는 것을 나타내는 포인터이다.

 

 

길이가 2일때도 일치하는 패턴이 없고 j는 그대로 0이다.

길이가 3일때도 일치하는 패턴이 없고 j는 그대로 0이다.

길이가 4일때는 j가 가리키는 A와 i가 가리키는 A가 일치하기 때문에 1을 저장한다.

그리고 j 값을 1증가

길이가 5일때는 B와 B가 일치한다. j증가시킨다

길이가 6일때는 일치하지 않는다.

 

0 0 0 1 2 0 이라는 값을 어떻게 이용할 수 있을까 예시를 들어보겠다.

 

A B D A B 까지 문자를 비교하면서 같은게나오다가 마지막에 D가 나왓다고 생각해보자.

그러면  다시 I+1로 가서 처음부터 비교해야할까?? 아니다.. Pi 배열을 이용하면

 

6번째에 틀렷으니 5번째까지는 다맞다는 소리다. 그러면 2번 째 항목이랑 i부터 다시검사하면 된다는것이다.

 

 

소스코드

package day0410;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class B16916 {
    
    static int[] getPi(String Pattern) {
        int[] pi = new int[Pattern.length()];
        
        int j = 0;
        
        for(int i=1;i<Pattern.length();i++) {
            
            while(j>0 && Pattern.charAt(i)!=Pattern.charAt(j)) {
                j = pi[j-1];
            }
            if(Pattern.charAt(i) == Pattern.charAt(j)) {
                pi[i] = ++j;
            }
        }
        return pi;
    }
    
    static int KMP(String Origin,String Pattern) {
        
        int j = 0 ;
        int[] pi = getPi(Pattern);
        for(int i=0;i<Origin.length();i++) {
            
            while(j>0 && Origin.charAt(i)!=Pattern.charAt(j)) {
                j = pi[j-1];
            }
            
            if(Origin.charAt(i) == Pattern.charAt(j)) {
                if(j == Pattern.length()-1) {
                    return 1;
                }else {
                    ++j;
                }
            }
            
            
        }
        
        return 0;
    }
    
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        String Origin = br.readLine();
        String Pattern = br.readLine();
        
        System.out.println(KMP(Origin, Pattern));
        
    }
}
 

 

 

package day0410;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class B1786 {
    static int[] getPi(String Pattern) {
        int[] pi = new int[Pattern.length()];
 
        int j = 0;
 
        for (int i = 1; i < Pattern.length(); i++) {
 
            while (j > 0 && Pattern.charAt(i) != Pattern.charAt(j)) {
                j = pi[j-1];
            }
            if (Pattern.charAt(i) == Pattern.charAt(j)) {
                pi[i] = ++j;
            }
        }
        return pi;
    }
 
    static StringBuilder sb = new StringBuilder();
    static int cnt = 0;
 
    static void KMP(String Origin, String Pattern) {
        int j = 0;
        
        int[] pi = getPi(Pattern);
        for (int i = 0; i < Origin.length(); i++) {
            while(j>0 && Pattern.charAt(j) != Origin.charAt(i)) {
                j = pi[j-1];
            }
            
            if(Pattern.charAt(j) == Origin.charAt(i)) {
                if(j == Pattern.length()-1) {
                    sb.append(i-j+1).append(' ');
                    cnt++;
                    j = pi[j];
                }else {
                    ++j;
                }
            }
        }
    }
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        String Origin = br.readLine();
        String Pattern = br.readLine();
        
        KMP(Origin,Pattern);
        
        System.out.println(cnt);
        System.out.println(sb.toString());
    }
}