KMP

문자열 매칭 알고리즘 : KMP

 

KMP 알고리즘은 접두사와 접미사의 개념을 활용하여 ‘반복되는 연산을 얼마나 줄일 수 있는지’를 판별하여, 매칭할 문자열을 빠르게 건너뛰는 기법이다.

 

makeTable() : 접두사와 접미사의 개념을 활용한 최대 일치 길이를 찾는 함수

연습 문제

boj 5525번 IOIOI

boj 1786번 찾기

import java.io.*;
import java.util.*;
 
public class Solution {
 
    static BufferedReader br;
    static BufferedWriter bw;
    
    // table 구축
    static Vector<Integer> makeTable(String pattern) 
    {
        int patternSize = pattern.length();
        
        Vector<Integer> table = new Vector<Integer>();
        
        for(int i=0; i<patternSize; i++) {
            table.add(0);
        }
 
        int j = 0;
        
        /* 일치하는 경우에는 i와 j 둘 다 증가시켜준다.
         * 일치하지 않는 경우에는 i는  증가, j는 현재 table 내에서 (j-1)번 째 인덱스의 값으로 바꿔준다.
         */
        
        for(int i=1; i<patternSize; i++) {
            while(j > 0 && pattern.charAt(i) != pattern.charAt(j))
            {
                j = table.get(j - 1);
            }
            
            if(pattern.charAt(i) == pattern.charAt(j)) {
                table.set(i, ++j);
            }
        }
        
        return table;
    }
    
    /* 매칭이 이루어지지 않는(실패한) 인덱스(index)에서 1을 뺀 인덱스(index - 1)가 가리키는
     * 그 값으로 j를 이동시킨다.
     * i는 계속 앞으로 나아가기만 하면 된다.
     */
    static void kmp(String parent, String pattern)
    {
        Vector<Integer> table = new Vector<Integer>();
        table = makeTable(pattern);
        
        int parentSize = parent.length();
        int patternSize = pattern.length();
        
        int j = 0;
        for(int i=0; i<parentSize; i++) {
            while(j > 0 && parent.charAt(i) != pattern.charAt(j)) 
            {
                j = table.get(j - 1);
            }
            
            if(parent.charAt(i) == pattern.charAt(j)) {
                if(j == patternSize - 1) {
                    System.out.println(i - patternSize + 2 + "번 째에서 찾았습니다.");
                    j = table.get(j); // 찾은 뒤에도 점프
                }
                else {
                    ++j;
                }
            }
        }
    }
 
    public static void main(String[] args) throws IOException  {
        // TODO Auto-generated method stub
        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        //st = new StringTokenizer(br.readLine());
        
        String parent = "ababacabacaabacaaba";
        String pattern = "abacaaba";
        
        kmp(parent, pattern);
 
        bw.write("\n");
        bw.flush();
        bw.close();
    }
}
 
class pair {
    int first, second;
    pair(int a, int b) {
        this.first = a;
        this.second = b;
    }
}
 
class tuple {
    int first, second, third;
    tuple(int a, int b, int c) {
        this.first = a;
        this.second = b;
        this.third = c;
    }
}
 
class PQ implements Comparable<PQ> {
    int first, second, third;
    
    PQ(int f, int s, int t) {
        this.first = f;
        this.second = s;
        this.third = t;
    }
    
    public int compareTo(PQ p) {
        if(this.first < p.first) {
            return -1; // 오름차순
        }
        else if(this.first == p.first) {
            if(this.second < p.second) {
                return -1;
            }
            else if(this.second == p.second) {
                if(this.third < p.third) {
                    return -1;
                }
            }
        }
        
        return 1; 
        // 이미 this.first가 더 큰 것이 됐으므로, 1로 해준다.
        // -1로 하면 결과가 이상하게 출력됨.
    }
}