[알고리즘 개념] KMP - 문자열 검색 알고리즘(JAVA 코드)

KMP란

문자열 검색 알고리즘.
Knuth-Morris-Pratt 3명의 사람이 설계한 알고리즘으로, 전체 문자열에서 특정 문자열을 찾는 알고리즘.

시간복잡도: N+M
N(전체 문자열 길이), M(패턴 문자열 길이)

 

브루트포스로 풀이 코드

가장 쉽게 생각할 수 있는 브루트포스로 전체 문자열에서 특정 문자열을 찾았다면,

시간복잡도는 전체 문자열의 길이(n) * 특정 문자열의 길이(m)

 

public Main{

  String all = "ABABABCD"; // 전체 문자열
  String pattern = "ABABC"; // 패턴

  int cnt = 0; //패턴이 맞은 개수

  for(int i = 0; i < all.length(); i++){
      boolean check = true; // 패턴이 맞는지 체크 변수
      for(int j = 0; j < pattern.length(); j++){
          if(all[i+j] != pattern[j]){
              check = false;
              break;
          }
          if(check){
              cnt++;
          }
      }
  }
}

1. i 0일때, j 4일때 맞지 않는게 체크

A	B	A	B	A	B	C	D
A	B	A	B	C

2. i 1,j 0 일때 맞지 않는게 체크

A	B	A	B	A	B	C	D
	A	B	A	B	C

3. i 2,j 0~4까지 체크하며 다 맞는게 확인. 패턴 맞은 개수 cnt 증가

A	B	A	B	A	B	C	D
		A	B	A	B	C

 

 

브루트포스 방식대로 진행한다면 위에서 말했다시피, n*m의 시간복잡도가 발생합니다

 

 

KMP 알고리즘

 

그런데 위의 표 1번상황에서 보면, A와 C가 불일치하기전에 ABAB까진 맞았던것을 확인가능합니다

맞은 패턴에서 ABAB 보면 AB가 반복되는것을 알 수 있습니다

ABAB 다음 C 에서 틀린것이니, 앞의 반복 AB를 뒤의 반복 AB로 가져다놓고 패턴을 다시 비교

A	B	A	B	A	B	C	D
A	B	A	B	C

ABAB까진 맞음.

A	B	A	B	A	B	C	D
		A	B	A	B	C

반복되는 AB가 있으니 패턴 앞의 AB를 패턴 뒤의 AB에 맞춰 재배치

A	B	A	B	A	B	C	D
		A	B	A	B	C

그러면 다시 안맞았던 부분부터 체크하면 된다.(다 맞으면 cnt 증가)

기존 브루트포스 방식대로라면,

전체문자열에 A에서 패턴 확인. B에서 패턴확인 형태로 N*M 만큼의 시간복잡도 발생.

KMP에선 맞았던 부분을 이용해 건너뛰고 체크하다 틀린부분에서 다시 체크하기때문에, N+M 시간복잡도 발생.

 

빨강 주황이 패턴내에 반복됨

앞의 빨강 주황을 뒤의 빨강 주황 자리에 맞춰서 땡김.

 

이러한 방법으로 시간복잡도를 줄인 알고리즘이 KMP입니다.

 

알고리즘 구현 순서

1) 패턴 내 일치 부분 찾기(배열저장)

• KMP는 접두사,접미사, 경계를 이용하여 일치부분을 찾습니다
• 접두사와 접미사는 어떤 단어의 앞과 뒤에 붙는 단어를 뜻함
• 여기에선 접두사는 왼쪽에서 만들어지는 문자열, 접미사는 오른쪽에서부터 만들어지는 문자열을 뜻함
•  

  ABABC(패턴 문자열)
  접두사	접미사
  A	B
  AB	AB
  ABA	BAB
  ABAB	BABC

• 경계는 접두사와 접미사가 일치할때, 그 길이를 뜻함.
• 경계를 저장할땐, 가장 큰 길이를 저장해둠. 
  • AB에서 일치 = 경계 2
• 이제 패턴 내에 일치부분 찾아서, 배열을 만들어 저장해뒀다가 쓰일겁니다.

  • 일치하는 패턴 문자열	접두사	접미사	경계길이
    A	없음	없음	0
    AB	A	B	0
    ABA	A, AB	A, BA	1
    ABAB	A, AB, ABA	B. AB, BAB	2
    ABABC	A, AB, ABA, ABAB	C, BC, ABC, BABC	0

  • Pi = {0,0,1,2,0};
• 배열 만드는 코드

// 패턴 일치 저장 배열
public static void getPi(){
    // j = 접두사, i 접미사
    int j = 0;
    // 패턴을 돌면서 체크
    for(int i = 1; i < pattern.length(); i++){
        // 처음 접두사가 아니면서 일치하지 않으면, 반복되는 패턴의 앞부분으로 변경
        // 만약 반복되는 패턴이 없으면, j = 0까지 돌아갈거임
        while(j > 0 && pattern.charAt(i) != pattern.charAt(j)){
            j = pi[j-1];
        }
        // 일치할때, 접두사의 길이(경계) 저장
        // 현재 맞은 idx의 +1은 길이이자, 다음 체크할 idx가 됨
        if(pattern.charAt(i) == pattern.charAt(j)){
            pi[i] = ++j;
        }
    }
}

 

2) 전체 문자열에서 KMP 실행

• 일치했던 패턴에서의 경계를 이용해서 건너뛰는 방식으로 체크한다.
• 건너뛰는 크기는 일치패턴길이 - 경계
• 위에서 구한 각 일치패턴의 경계 길이 Pi = {0,0,1,2,0};
•   

  A	B	A	B	A	B	C	D
  A	B	A	B	C

  ABAB까진 맞음. Pi[3] = 2 의 경계를 가지고, 전체 일치 패턴 길이(4) - 경계(2) = 2만큼 이동

• A	B	A	B	A	B	C	D
  		A	B	A	B	C

• 이동 후, 불일치부분 다시 체크
• 코드

public static void kmp(){
        // 패턴 내 일치체크 idx
        int j = 0;
        // 전체 문자열 돌기
		for (int i = 0; i < all.length(); i++) {
			// 맞는 위치가 나올 때까지 j - 1칸의 공통 부분 위치로 이동
			while(j > 0 && all.charAt(i) != pattern.charAt(j)) {
				j = pi[j - 1];
			}
			// 맞는 경우 패턴의 끝까지 확인했으면 정답
			if(all.charAt(i) == pattern.charAt(j)) {
				if(j == pattern.length() - 1) {
					answer = 1;
					break;
                // 아니면 패턴의 다음 문자를 확인
				}else{
                    j++;
                }
			}
		}
	}

 

 

전체코드(백준 16916 _ 부분문자열 문제)

https://www.acmicpc.net/problem/16916

/**
 * 전체 문자열과 패턴이 주어졌을때,
 * 
 * 전체 문자열에 패턴이 존재하는지 확인
 * 
 * KMP 사용 풀이
 */

import java.util.*;
import java.io.*;

public class BJ16916_부분문자열 {
    
    public static int answer,pi[];
    public static String all,pattern;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    
        all = br.readLine();
        pattern = br.readLine();

        pi = new int[pattern.length()];

        getPi();
        kmp();
        System.out.println(answer);

    }

    // 패턴 일치 저장 배열
    public static void getPi(){
        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;
            }
        }
    }
    
    public static void kmp(){
        // 패턴 내 일치체크 idx
        int j = 0;
        // 전체 문자열 돌기
		for (int i = 0; i < all.length(); i++) {
			// 맞는 위치가 나올 때까지 j - 1칸의 공통 부분 위치로 이동
			while(j > 0 && all.charAt(i) != pattern.charAt(j)) {
				j = pi[j - 1];
			}
			// 맞는 경우 패턴의 끝까지 확인했으면 정답
			if(all.charAt(i) == pattern.charAt(j)) {
				if(j == pattern.length() - 1) {
					answer = 1;
					break;
                    //패턴이 있는지가 아닌 몇개 있는지 찾는거면
                    // answer++; : 개수증가
                    // j = pi[j]; : j 초기화
                // 아니면 패턴의 다음 문자를 확인
				}else{
                    j++;
                }
			}
		}
    }
}

 

 

 

 

참조

https://chanhuiseok.github.io/posts/algo-14/

알고리즘 - KMP 알고리즘 : 문자열 검색을 위한 알고리즘