[Python] 백준 - 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 알고리즘 설명 링크

 

Injae's devlog

 

설명이 잘되어 있는 포스트가 많은데, 개인적으로 가장 쉬운 방법으로 잘 이해되는 것 같은 포스트다.
현재 실제로 사용되고 있는 문자열 검색 알고리즘은 해쉬테이블을 이용해서 해쉬값이 동일할 때, 문자열이 맞는지 맞춰보는 알고리즘이 사용된다고 한다. KMP알고리즘의 개념이 다른 경우에 활용할 중복계산을 방지하는 아이디어가 될 수도 있다.
 
 

문제해결방법

 
1. pi함수로 검색할 텍스트에서도 테이블을 구한다. 테이블은 접두사이면서 접미사인 최대문자열의 길이(혹은 다음위치)가 각 문자열의 인덱스마다 구해져서 저장된다. (이는 중복계산을 방지하는 장치가 된다.)
 
※ 접두사, 접미사는 사전적 의미보다는 문제상 중복을 배제할 수 있는 겹치는 문자열구간의 앞번째, 뒤번째라고 보면 된다.
 
2. 위 함수로 구한 테이블을 활용하여, 검색대상 텍스트에서 검색할 텍스트의 길이가 전부 채워지면 그 위치를 ans에 저장한다.
 
 

- pi 함수에 대해서

(예제는 개인적으로 이해가 쉬웠던 예제이다.)

import sys
import heapq
import math
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

s = list(input().rstrip())
d = list(input().rstrip())

def pi(string):
    table = [0 for _ in range(len(string))]
    idx = 0
    for i in range(1, len(string)):
        while idx > 0 and string[idx] != string[i]:
            idx = table[idx-1]
        if string[idx] == string[i]:
            idx += 1
            table[i] = idx
    return table

print(pi('AABAABXAABAABA'))
'''
 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,10,11,12,13
 A  A  B  A  A  B  X  A  A  B  A  A  B  A
[0, 1, 0, 1, 2, 3, 0, 1, 2, 3, 4, 5, 6, 4]
'''

 
1. 위 코드의 주석 부분처럼 테이블이 구성된다.
                                                                                      
 

i	0	1	2	3	4	5	6	7	8	9	10	11	12	13
string	A	A	B	A	A	B	X	A	A	B	A	A	B	A
table	0	1	0	1	2	3	0	1	2	3	4	5	6	4

 
1) 테이블의 값은 접두사, 접미사의 길이 혹은 접두사의 다음 위치가 저장된다.
2) i < 12 일 때, 진행은 그리 어렵지 않고, 천천히 따라가보면 된다.
3) i = 12 일 때, idx는 6까지 증가되었지만, 13번째 string[i]와 6번째인 string[idx]는 같지 않다.
 
이 경우, idx = table[idx-1]이 되어 idx는 table[5]의 값인 3이 된다. << 여기에서 table[5]를 불러오는 이유는 6번째 idx(X)까지 진행되었지만, 같지 않았기 때문에 그 전의 같았던 경우(idx가 5번째였을 때)의 접두사, 접미사 길이 혹은 접두사의 다음 위치를 불러온다는 것이다. (AABAAB에 저장된 접두사, 접미사의 최대문자열길이 혹은 접두사 다음위치)
 
불러온 table[5] = 3은 AABAAB이 [0, 1, 0, 1, 2, 3]이고, 첫 문자열 AAB의 다음 위치(i = 3), 혹은 접두사, 접미사의 최대문자열 길이가 저장되어 있다는 걸 알 수 있다.(혹은 접두사 다음 위치) 해당 테이블 값과 string[i]가 또 같지 않으면, 재귀함수마냥 중복계산을 방지하려는 범위가 줄어들고, idx가 0이 되어 while문이 종료되거나, 같은 경우를 찾아 다음 위치를 테이블에 반영한다는 것을 알 수 있다. (이 경우, idx = 3에서 string[i]가 동일하기 때문에 idx += 1되어 테이블에 4가 저장된다.)
 
AABAAB 범위에서 AAB로 범위가 줄어들었다. 만약 13번째인 'A'가 'X'였다면 table[13]은 7이 되었을 것이다.
또 string[3]이 string[13]과 또 같지 않았다면, idx는 0으로 다시 돌아갈 수밖에 없다.
 
2. 이렇게 구성된 테이블은 검색대상 텍스트에서 신나게 맞춰가다 마지막에 다를 경우가 반복될 때, 중복계산을 줄여주는 역할을 하게 된다.
 

- 코드

import sys
import heapq
import math
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

s = list(input().rstrip())
d = list(input().rstrip())

def pi(s):
    table = [0 for _ in range(len(s))]
    idx = 0
    for i in range(1, len(s)):
        while idx > 0 and s[i] != s[idx]:
            idx = table[idx-1] 
        if s[i] == s[idx]:      
            idx += 1
            table[i] = idx
    return table

def kmp(s, d):
    table = pi(d)
    ans = []
    idx = 0
    for i in range(len(s)):
        while idx > 0 and s[i] != d[idx]:
            idx = table[idx-1]
        if s[i] == d[idx]:
            if idx == len(d)-1:
                ans.append(i-len(d)+2)
                idx = table[idx]
            else:
                idx += 1
    return ans

ans = kmp(s, d)
print(len(ans))
print(*ans)