[BOJ] 백준 1786번 찾기 (Java)

#1786 찾기

난이도 : 플레 5

유형 : 문자열 / KMP

1786번: 찾기

첫째 줄에, T 중간에 P가 몇 번 나타나는지를 나타내는 음이 아닌 정수를 출력한다. 둘째 줄에는 P가 나타나는 위치를 차례대로 공백으로 구분해 출력한다. 예컨대, T의 i～i+m-1번 문자와 P의 1～m

www.acmicpc.net

▸ 문제

워드프로세서 등을 사용하는 도중에 찾기 기능을 이용해 본 일이 있을 것이다. 이 기능을 여러분이 실제로 구현해 보도록 하자.

두 개의 문자열 P와 T에 대해, 문자열 P가 문자열 T 중간에 몇 번, 어느 위치에서 나타나는지 알아내는 문제를 '문자열 매칭'이라고 한다. 워드프로세서의 찾기 기능은 이 문자열 매칭 문제를 풀어주는 기능이라고 할 수 있다. 이때의 P는 패턴이라고 부르고 T는 텍스트라고 부른다.

편의상 T의 길이를 n, P의 길이를 m이라고 하자. 일반적으로, n ≥ m이라고 가정해도 무리가 없다. n<m이면 어차피 P는 T중간에 나타날 수 없기 때문이다. 또, T의 i번째 문자를 T[i]라고 표현하도록 하자. 그러면 물론, P의 i번째 문자는 P[i]라고 표현된다.

      1 2 3 4 5 6 7 8 9 …
T : [ A B C D A B C D A B D E ]
      | | | | | | X
P : [ A B C D A B D ]
      1 2 3 4 5 6 7

문자열 P가 문자열 T 중간에 나타난다는 것, 즉 문자열 P가 문자열 T와 매칭을 이룬다는 것이 어떤 것인지 위와 아래의 두 예를 통해 알아보자. 위의 예에서 P는, T의 1번 문자에서 시작하는 매칭에 실패했다. T의 7번 문자 T[7]과, P의 7번 문자 P[7]이 서로 다르기 때문이다.

그러나 아래의 예에서 P는, T의 5번 문자에서 시작하는 매칭에 성공했다. T의 5～11번 문자와 P의 1～7번 문자가 서로 하나씩 대응되기 때문이다.

      1 2 3 4 5 6 7 8 9 …
T : [ A B C D A B C D A B D E ]
              | | | | | | |
P :         [ A B C D A B D ]
              1 2 3 4 5 6 7

가장 단순한 방법으로, 존재하는 모든 매칭을 확인한다면, 시간복잡도가 어떻게 될까? T의 1번 문자에서 시작하는 매칭이 가능한지 알아보기 위해서, T의 1～m번 문자와 P의 1～m번 문자를 비교한다면 최대 m번의 연산이 필요하다. 이 비교들이 끝난 후, T의 2번 문자에서 시작하는 매칭이 가능한지 알아보기 위해서, T의 2～m+1번 문자와 P의 1～m번 문자를 비교한다면 다시 최대 m번의 연산이 수행된다. 매칭은 T의 n-m+1번 문자에서까지 시작할 수 있으므로, 이러한 방식으로 진행한다면 O( (n-m+1) × m ) = O(nm) 의 시간복잡도를 갖는 알고리즘이 된다.

더 좋은 방법은 없을까? 물론 있다. 위에 제시된 예에서, T[7] ≠ P[7] 이므로 T의 1번 문자에서 시작하는 매칭이 실패임을 알게 된 순간으로 돌아가자. 이때 우리는 매칭이 실패라는 사실에서, T[7] ≠ P[7] 라는 정보만을 얻은 것이 아니다. 오히려 i=1…6에 대해 T[i] = P[i] 라고 하는 귀중한 정보를 얻지 않았는가? 이 정보를 십분 활용하면, O(n)의 시간복잡도 내에 문자열 매칭 문제를 풀어내는 알고리즘을 설계할 수 있다.

P 내부에 존재하는 문자열의 반복에 주목하자. P에서 1, 2번 문자 A, B는 5, 6번 문자로 반복되어 나타난다. 또, T의 1번 문자에서 시작하는 매칭이 7번 문자에서야 실패했으므로 T의 5, 6번 문자도 A, B이다.

따라서 T의 1번 문자에서 시작하는 매칭이 실패한 이후, 그 다음으로 가능한 매칭은 T의 5번 문자에서 시작하는 매칭임을 알 수 있다! 더불어, T의 5～6번 문자는 P의 1～2번 문자와 비교하지 않아도, 서로 같다는 것을 이미 알고 있다! 그러므로 이제는 T의 7번 문자와 P의 3번 문자부터 비교해 나가면 된다.

이제 이 방법을 일반화 해 보자. T의 i번 문자에서 시작하는 매칭을 검사하던 중 T[i+j-1] ≠ P[j]임을 발견했다고 하자. 이렇게 P의 j번 문자에서 매칭이 실패한 경우, P[1…k] = P[j-k…j-1]을 만족하는 최대의 k(≠j-1)에 대해 T의 i+j-1번 문자와 P의 k+1번 문자부터 비교를 계속해 나가면 된다.

이 최대의 k를 j에 대한 함수라고 생각하고, 1～m까지의 각 j값에 대해 최대의 k를 미리 계산해 놓으면 편리할 것이다. 이를 전처리 과정이라고 부르며, O(m)에 완료할 수 있다.

이러한 원리를 이용하여, T와 P가 주어졌을 때, 문자열 매칭 문제를 해결하는 프로그램을 작성하시오.

▸ 입력

첫째 줄에 문자열 T가, 둘째 줄에 문자열 P가 주어진다. T와 P의 길이 n, m은 1이상 100만 이하이고, 알파벳 대소문자와 공백으로만 이루어져 있다.

▸ 출력

첫째 줄에, T 중간에 P가 몇 번 나타나는지를 나타내는 음이 아닌 정수를 출력한다. 둘째 줄에는 P가 나타나는 위치를 차례대로 공백으로 구분해 출력한다. 예컨대, T의 i～i+m-1번 문자와 P의 1～m번 문자가 차례로 일치한다면, i를 출력하는 식이다.

문제 풀이

문제에서 친절하게 KMP알고리즘으로 풀이를 하라고 제시되어있다. KMP알고리즘은 어떻게 효율적으로 동작하는지 간단하게 다뤄보자.

단순 문자열 매칭

가장 단순한 문자열 매칭은 이중포문으로 O(NM)이라는 시간복잡도를 갖게되어 큰 문자열이 주어질 때는 사용하기 부적절하다.

static int findString(String parent, String pattern) {
	int n1 = parent.length();
	int n2= pattern.length();
	for(int i=0; i<=n1-n2; i++) {
		boolean flag = true;
		for(int j=0; j<n2; j++) {
			if(parent.charAt(i+j) != pattern.charAt(j)) {
				flag = false;
				break;
			}
		}

		if(flag) {
			return 1; // 문자열을 찾으면 1
		}
	}
	return 0; // 찾지 못했으면 0 
}

KMP 문자열 매칭 알고리즘

KMP는 접두사와 접미사의 개념을 활용하여 모든 경우를 계산하지 않고 반복되는 연산을 줄여나가 매칭 문자열을 빠르게 점프하는 기법으로 효율적으로 문자열 매칭을 이루어나간다. 문자열 매칭 중 불일치가 일어났을 때 지금까지 일치한 글자의 수를 이용해 다음으로 시도해야 할 시작 위치를 빠르게 찾아낸다.

KMP 알고리즘을 동작시키기 위해서는 접두사도 되고 접미사도 되는 문자열의 최대 길이를 저장해주는 table을 미리 정의해줘야한다. table[]은 pattern이 어디까지 일치했는지가 주어질 때 다음 시작 위치를 어디로 해야할지를 말해주기 때문에, 이를 흔히 부분 일치 테이블이라고 부른다.

table[i] = pattern(0...i)의 접두사도 되고 접미사도 되는 문자열의 최대 길이

i	pattern(0...i)	접두사이면서 접미사인 최대 문자열	table[i]
0	A	(없음)	0
1	AB	(없음)	0
2	ABC	(없음)	0
3	ABCD	(없음)	0
4	ABCDA	A	1
5	ABCDAB	AB	2
6	ABCDABD	(없음)	0

중요한 점은 시작 위치를 움직인 이후 첫 글자부터 다시 대응시켜 나갈 필요가 없다는 것이다. 새로운 위치에서 비교를 시작하더라도 pattern의 첫 table[matched-1] 글자를 대응되는 parent의 글자와 알치한다는 사실을 이미 알고 있기 때문이다. 따라서 matched를 table[matched-1]으로 변경하고 비교를 계속하면 된다.

KMP 알고리즘의 전통적인 구현

다음은 KMP 알고리즘의 전통적인 구현 방식이다.

begin = matched = 0 부터 탐색을 시작한다.
만약 pattern과 parent의 해당 글자가 일치한다면 if(matched < n2 && parent.charAt(begin+matched) == pattern.charAt(matched))
1. matched 카운트를 증가시켜 준다. matched++;
2. match된 글자가 pattern글자의 총 길이와 일치했다면 답에 추가한다.
만약 pattern과 parent의 해당 글자가 일치하지 않는다면
1. matched가 0인 경우 다음 칸에서 계속한다.
2. begin의 위치를 옮겨준다. begin += matched - table[matched-1];
  1. 옮겼다고 처음부터 다시 비교할 필요가 없다. table[matched-1]만큼은 항상 일치하기 때문이다.

static void KMP(String parent, String pattern){
	int[] table = makeTable(pattern);
	
	int n1 = parent.length(), n2 = pattern.length();
	int begin =0, matched=0;
	int cnt=0;
	StringBuilder sb = new StringBuilder();
	while(begin <= n1-n2) {
		// 만약 짚더미의 해당 글자가 바늘의 해당 글자가 같다면
		if(matched < n2 && parent.charAt(begin+matched) == pattern.charAt(matched)) {
			++matched;
			// 결과적으로 m글자가 모두 일치했다면 답에 추가한다.
			if(matched == n2) {
				sb.append((begin+1)+" ");
				cnt++;
			}
		}else{
			// 예외 : matched가 0인 경우에는 다음 칸에서부터 계속 
			if(matched ==0) {
				++begin;
			}else {
				// begin을 옮겼다고 처음부터 다시 비교할 필요가 없다.
				// 옮긴 후에도 table[matched-1]만큼은 항상 일치하기 때문이다.
				begin += matched - table[matched-1];
				matched = table[matched-1];
			}
		}
	}
	System.out.println(cnt);
	System.out.println(sb.toString());
}

KMP 알고리즘의 다른 구현

전통적인 구현은 KMP 알고리즘을 처음 제안한 논문에서 부보인 구현으로 이해가 조금 까다롭다. 해당 알고리즘은 더욱 간결하기 때문에 자주 볼 수 있으며 KMP 알고리즘을 응용해 다른 알고리즘을 만드는 기반으로도 더 유용하게 쓰일 수 있다.

i = matched + begin, idx = matched 라고 생각하면 위와 동일하다.

static void KMP2(String parent, String pattern){
	int[] table = makeTable(pattern);
	
	int n1 = parent.length(), n2 = pattern.length();
	int idx=0; // 현재 대응되는 글자 수
	int cnt=0;
	StringBuilder sb = new StringBuilder();
	for(int i=0; i<n1; i++) {
		// idx번 글자와 짚더미의 해당 글자가 불일치할 경우, 
		// 현재 대응된 글자의 수를 table[idx-1]번으로 줄인다.
		while(idx>0 && parent.charAt(i) != pattern.charAt(idx)) {
			idx = table[idx-1];
		}
		// 글자가 대응될 경우	
		if(parent.charAt(i) == pattern.charAt(idx)) {
			if(idx == n2-1) {
				sb.append((i-idx+1)+" ");
				System.out.println("find" + (i-idx+1) + " ~ " + (i+1));
				cnt++;
				idx = table[idx];
			}else {
				idx +=1;
			}
		}
	}
	
	System.out.println(cnt);
	System.out.println(sb.toString());
}

KMP 풀이 코드 1 (전통적인 방식)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String t = br.readLine();
		String p = br.readLine();
		
		KMP(t,p);
	}
	static void KMP(String parent, String pattern){
		int[] table = makeTable(pattern);
		
		int n1 = parent.length(), n2 = pattern.length();
		int begin =0, matched=0;
		int cnt=0;
		StringBuilder sb = new StringBuilder();
		while(begin <= n1-n2) {
			if(matched < n2 && parent.charAt(begin+matched) == pattern.charAt(matched)) {
				++matched;
				if(matched == n2) {
					sb.append((begin+1)+" ");
					cnt++;
				}
			}else{
				if(matched ==0) {
					++begin;
				}else {
					begin += matched - table[matched-1];
					matched = table[matched-1];
				}
			}
		}
		System.out.println(cnt);
		System.out.println(sb.toString());
		
	}
	static int[] makeTable(String pattern) {
		int n = pattern.length();
		int[] table = new int[n];
		int idx = 0;
		for(int i=1; i<n; i++) {
			while(idx>0 && pattern.charAt(i) != pattern.charAt(idx)) {
				idx = table[idx-1];
			}
			if(pattern.charAt(i) == pattern.charAt(idx)) {
				table[i] = ++idx;
			}
		}
		return table;
	}
}

KMP 풀이 코드 2 (다른 구현 방식)

전통적인 구현 방식보다 간단하므로 해당 방식으로 많이 사용된다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String t = br.readLine();
		String p = br.readLine();
        
		KMP(t,p);
	}
	static void KMP(String parent, String pattern){
		int[] table = makeTable(pattern);
		
		int n1 = parent.length(), n2 = pattern.length();
		int idx=0;
		int cnt=0;
		StringBuilder sb = new StringBuilder();
		for(int i=0; i<n1; i++) {
			while(idx>0 && parent.charAt(i) != pattern.charAt(idx)) {
				idx = table[idx-1];
			}
			
			if(parent.charAt(i) == pattern.charAt(idx)) {
				if(idx == n2-1) {
					sb.append((i-idx+1)+" ");
					cnt++;
					idx = table[idx];
				}else {
					idx +=1;
				}
			}
		}
		
		System.out.println(cnt);
		System.out.println(sb.toString());
		
	}
	
	static int[] makeTable(String pattern) {
		int n = pattern.length();
		int[] table = new int[n];
		
		int idx = 0;
		for(int i=1; i<n; i++) {
			while(idx>0 && pattern.charAt(i) != pattern.charAt(idx)) {
				idx = table[idx-1];
			}
			if(pattern.charAt(i) == pattern.charAt(idx)) {
				table[i] = ++idx;
			}
		}
		return table;
	}
}

'Dot Algo∙ DS > PS' 카테고리의 다른 글

[BOJ] 백준 4354번 문자열 제곱 (Java) (0)	2021.11.21
[BOJ] 백준 1305번 광고 (Java) (0)	2021.11.20
[BOJ] 백준 17143번 낚시왕 (Java) (0)	2021.11.18
[BOJ] 백준 2668번 숫자고르기 (Java) (0)	2021.11.17
[BOJ] 백준 2665번 미로만들기 (Java) (0)	2021.11.16

그릿 속의 해빗

[BOJ] 백준 1786번 찾기 (Java)

#1786 찾기

▸ 문제

▸ 입력

▸ 출력

문제 풀이

단순 문자열 매칭

KMP 문자열 매칭 알고리즘

KMP 알고리즘의 전통적인 구현

KMP 알고리즘의 다른 구현

KMP 풀이 코드 1 (전통적인 방식)

KMP 풀이 코드 2 (다른 구현 방식)

'Dot Algo∙ DS > PS' 카테고리의 다른 글

티스토리툴바

티스토리툴바

« 2024/11 »
일	월	화	수	목	금	토
					1	2
3	4	5	6	7	8	9
10	11	12	13	14	15	16
17	18	19	20	21	22	23
24	25	26	27	28	29	30

[BOJ] 백준 1786번 찾기 (Java)

#1786 찾기

▸ 문제

▸ 입력

▸ 출력

문제 풀이

단순 문자열 매칭

KMP 문자열 매칭 알고리즘

KMP 알고리즘의 전통적인 구현

KMP 알고리즘의 다른 구현

KMP 풀이 코드 1 (전통적인 방식)

KMP 풀이 코드 2 (다른 구현 방식)

'Dot Algo∙ DS > PS' 카테고리의 다른 글

'Dot Algo∙ DS/PS' 관련글

티스토리툴바

티스토리툴바