백준 1786번: 찾기 (JAVA)

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

1786번: 찾기

문제

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

두 개의 문자열 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를 이해하지 못했으므로(실패함수??? 몰?루.) 라빈-카프를 활용하였다. 라빈-카프 알고리즘은 간단하게 말해서 주어진 문자열을 'a진법 (mod p)'로 해싱하여 문자열을 비교하는 알고리즘이라 할 수 있다.

여기서 a가 primitive root modulo p(https://en.wikipedia.org/wiki/Primitive_root_modulo_n 참고.)가 되도록 설정하여, 해싱 충돌 확률을 낮춘다. 예를 들어, a는 p에 대한 primitive root이 아닌 a == 2, p == 7라는 값이 있다면, a^4 = a (mod p)이며, 이런 경우 "ABCD"랑 "DBCA"는 같은 해시값을 같게 된다.

그리고 해싱 충돌은 p가 클 수록 줄어들기에, 적당히 큰 p를 선택한 후 primitive root modulo p인 a를 선택하여 푼다. 만약 해시값이 같다면 문자열을 하나하나 비교하여 같은지 확인해야 하는데, 이 과정을 다 확인한다면 O(MN) (M: 주어진 문자열의 길이, N: 찾고자 하는 문자열의 길이) time complexity가 된다. Wikipedia(https://en.wikipedia.org/wiki/Rabin%E2%80%93Karp_algorithm)의 라빈-카프 알고리즘 유사코드에 따르면 해시값이 같으면 문자열을 비교하여 같은지 확인한다고 써있지만, 바킹독 선생님의 글(https://blog.encrypted.gg/857)에 따르면 그렇게 쓸거면 (worst case때문에) 쓸 이유가 없으니 p를 매우 크게 한 후, 해싱값이 같으면 실제 문자열도 동일하다고 여기면서 문제를 풀라고 한다. 또한, 또다른 a', p'에 대하여 라빈-카프를 적용하여 더블-체크하면 확률이 곱으로 떨어진다고 한다.

- 이 문제에서는 바킹독 선생님 글에서 사용한대로 a =302, p = 1_000_000_007(PS에서 국룰 소수)를 사용한다.

 

풀이 방법

주어진 문자열 T, P가 있을 때, 만약 P가 T보다 길다면 P가 T의 부분문자열일 수 없다: 0 출력하고 끝.

T의 길이가 P의 길이보다 크거나 같으면 P의 해시값을 구하고, T의 해시값을 구한다. 해시값이 같은 지 확인하며, 이후 T를 슬라이딩 윈도우 하듯이 옮기면서 P의 해시값과 같은지 계속 비교하면 된다.

T에서의 부분 문자열을 옮길 때, (빠지는 문자의 값) * a^(P의 길이-1)을 빼고 a를 곱하고 (들어오는 문자의 값)을 더하면 되는데, a^(P의 길이-1)를 매번 곱하면 이거 자체가 O(MN)^[각주:1] 연산이다: 따라서, 미리 곱해둔 값을 저장하여 필요할 때마다 가져다 쓰자.

 

배운 점(사소하다)

JAVA에서의 modulo 연산 %는 수학에서의 mod와 다르게, dividend(피제수)의 부호랑 같은 값을 내뱉어서 직관적이지 않다. 그래서, 너무 정확한 modulo값을 구하려고 신경쓰기보다는 그냥 integer overflow가 안 나는 목적 정도로 modulo 연산을 해주고, 해시값이 같은지는 두 해시값을 뺀 값이 mod p에 대해 0인지 확인하는 식으로 풀자. 혹시 정확한 modulo값을 구하고 싶으면 Math.floormod를 사용하면 된다.

 

코드

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

public class Main {
	static int p = 1_000_000_007;
	static int a = 302;
	
	public static void main(String[] args) throws IOException{
		StringBuilder sb = new StringBuilder();
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String T = br.readLine();
		String P = br.readLine();
		int count = 0;
		
		long[] primeTable = new long[P.length()];
		long num = 1;
		for (int i = 0; i < primeTable.length; i++) {
			primeTable[P.length()-1-i] = num;
			num *= a;
			num = (num + p) % p;
		}
		//System.out.println(Arrays.toString(primeTable));
		
		if (P.length() > T.length()) System.out.println(0);
		else {
			long hashT = 0, hashP = 0;
			for (int i = 0; i < P.length(); i++) {
				hashT += T.charAt(i) * primeTable[i];
				hashP += P.charAt(i) * primeTable[i];
				hashT %= p;
				hashP %= p;
			}
			if ((hashT-hashP) % p == 0) {
				count++;
				sb.append(1+" ");
			}
			
			for (int i = 0; i < T.length() - P.length(); i++) {
				hashT -= T.charAt(i) * primeTable[0];
				hashT %= p;
				hashT *= a;
				hashT += T.charAt(i+P.length());
				hashT %= p;
				if ((hashT-hashP) % p == 0) {
					count++;
					sb.append(i+2+" ");
				}
				//System.out.println(hashT + " " + hashP);
			}
			System.out.println(count);
			System.out.println(sb);
		}
	}

	
	static long hashing(String str) {
		long ans = 0;
		for (int i = 0; i < str.length(); i++) {
			ans *= a;
			ans += str.charAt(i);
			ans %= p;
		}
		return ans % p;
	}
	
	static long squareP(char chr, int size) {
		long ans = (long) chr;
		for (int i = 0; i < size-1; i++) {
			ans *= a;
			ans %= p;
		}
		return ans % p;
	}
}

 

 

 

풀이 - KMP (22.02.25 추가)

KMP의 기본 개념을 설명하기엔 내가 그래픽 툴을 잘 다루지 못하며, 설명을 잘 하지도 못하기에 좋은 링크 글로 갈음한다. 전 세계에 사람은 많고 좋은 글은 많이 있다.

그렇기에 좋은 설명을 담은 링크를 첨부한다.

(비추천) 영문 위키피디아 → 봐도 뭔 소린지 모른다.

(추천) https://bowbowbow.tistory.com/6

KMP : 문자열 검색 알고리즘

(추천) https://blog.encrypted.gg/857

[실전 알고리즘] 0x0E강 - 문자열(KMP, 라빈 카프)_구버전

 

핵심을 내 나름의 언어로 정리하자면,

(문자열 S에 대한) 실패 함수 F(n): S의 처음부터 시작되는 길이 n+1의 부분 문자열에서 길이가 k인 prefix랑 suffix가 같게 되는 최대의 k. 단, k는 n보다 같거나 작다(생각해보면, k = n+1일 때에는 prefix == suffix == 기존 문자열이 자명하게 성립한다).

이후 F(n)을 O(N)에 구하는 알고리즘을 보면, 다른 건 그럭저럭 이해가 되나 'j > 0일 때 F(j-1)값 만큼 j를 감소시킨다'가 가장 이해가 안 될 것이다. 이를 말로 풀자면, 길이가 j인 문자열(이전까지는 동일했기에 j를 증가시킨 것이므로)에서 길이가 k인 suffix랑 prefix가 같게 되는 최대 k를 찾아야 하며, 이는 실패 함수 F(j-1)의 정의랑 같다. 

사실 코드로 짜라 하면 이 부분만 외우고 나머지는 머리속에서 때워도 될 듯하다. 다만 이러면 응용 문제는 못 풀겠지...?

 

 

KMP를 활용한 문제 풀이

백준 1305번: 광고 (https://www.acmicpc.net/problem/1305)

주어진 문자열의 길이가 N이라면, N-F(N-1)이 정답이다. 이 점에 대한 완전한 합리화는 하지 못하였지만, 앞에서 반복된 문자열이 얼마나 나오는건 큰 상관 없으며 뒤에서 F(N-1)만큼 중복되는 값이 있다면 이는 '광고 문구가 순환하여 출력되면서 나오는 값'이라고 볼 수 있어서 그런 듯하다.

 

코드

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

public class Main {

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        String str = br.readLine();
        int[] f = failure(str);
        //System.out.println(Arrays.toString(f));
        System.out.println(N-f[N-1]);
    }

    static int[] failure (String S) {
        int[] f = new int[S.length()];
        int j = 0;
        for (int i = 1; i < S.length(); i++) {
            while (S.charAt(i) != S.charAt(j) && j > 0) j = f[j-1];
            if (S.charAt(i) == S.charAt(j)) f[i] = ++j;
        }
        return f;
    }
}

 

백준 4354번: 문자열 제곱

테스트케이스를 바꿔가며 적어보다 보면, N - F(N-1)이 '반복되는 문자열의 주기'임을 알 수 있다. 제곱이 되야하기에, 주기는 N의 약수여야 한다. 만약 약수라면 N / (N - F(N-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 str;
		while (!(str = br.readLine()).equals(".")) {
			int N = str.length();
			int[] fails = failure(str);
			if (fails[N-1] == 0 || N % (N - fails[N-1]) != 0) System.out.println(1);
			else System.out.println(N / (N - fails[N-1]));
		}
	}
	
	static int[] failure(String S) {
		int[] f = new int[S.length()];
		int j = 0;
		for (int i = 1; i < S.length(); i++) {
			while (S.charAt(i) != S.charAt(j) && j > 0) j = f[j-1];
			if (S.charAt(i) == S.charAt(j)) f[i] = ++j;
		}
		
		return f;
	}
}

1. N제곱을 분할정복 기법으로 계산하면 O(MlogN)이긴 하지만, 비효율적이라는 점은 동일하다. [본문으로]