백준 1786 찾기

문제

👀 문제 사이트 : https://www.acmicpc.net/problem/1786

문제 : 두 개의 문자열 t, p가 주어질 때 p가 t안에 몇 번 등장하고, 몇 번째 위치에서 등장하는지 출력한다.

풀이

난이도 : Platinum V

자주 나오는 문자열 패턴매칭 문제로써 다양한 풀이방법이 존재한다.
구현하기 까다로운 KMP algorithm이나 유용성이 좋은 suffix array 등도 존재하지만, 문제 풀이로 z algorithm을 사용하였다.

z-algorithm

z algorithm에서 z array는 문자열 s에서 시작하는 substring 중 prefix이면서 가장 긴 substring의 길이를 저장한다.
z array는 O(n) 시간안에 구현할 수 있다.

예)
ABCABCABAB
[0, 0, 0, 5, 0, 0, 2, 0, 2, 0]

구현 방법

start index x와 end index y를 0으로 초기화해준다. (이후에 패턴매칭이 되는 곳이 있으면 그곳에 시작 index와 끝 index로 저장될 예정)
구현 방법은 3가지 case로 나누어 생각해볼 수 있다.

반복문을 돌면서 값을 채워줄 것이고, 반복문에서 해당 index를 k로 둔다.

1) k > y 일 경우

• 이 경우는 앞에서부터 전부 비교하면서 x와 y의 값을 찾고, y-x(문자열 길이) 값을 z array에 넣어주면 된다.
• 패턴 매칭이 안될 경우 자연스럽게 0이 기록된다.

2) k <= y && z[k-x] < y-k+1 일 경우

• i = k - x 로 두자. (prefix에서부터 떨어져있는 거리를 현재 탐색하는 index - x로 둔다.)
• 문자열을 s로 두자.
• s[i:] 와 s[k:]는 최소 y-k+1개는 일치하므로 y-k+1이 z[i]보다 작을 경우 z[k]값을 z[i]값과 동일하게 넣어준다.

3) k <= y && z[k-x] >= y-k+1 일 경우

• 2번과 다르게 z[i] 값이 y-k+1보다 같거나 클 경우에는 앞서 탐색하며 정해준 y값의 범위를 벗어날 수 있다.
• 따라서 x를 k로 두고, 다시 1번과 같이 y값을 탐색해주면 된다.

응용

z array를 이용하여 이 문제처럼 pattern matching에 관련된 문제를 푸는 방법은 아래와 같다.

예)
p = AB
t = ABCDABCDABDD

일 때,

s = p + "#" + t 로 둔다. -> AB#ABCDABCDABDD

z = [0, 0, 0, 2, 0, 0, 0, 2, 0, 0, 0, 2, 0, 0, 0]

-> p의 길이 : 2와 같은 값을 가지는 구간이 pattern matching이 되는 곳의 시작지점이다.

p와 t사이에 있는 값은 꼭 '#'이 아니어도 되며 문자열에 등장하지 않는 특수문자면 상관없다.
이렇게 문자열과 문자열 사이에 사용하지 않는 특수문자를 두고 합친 다음 z array를 만든 후에 앞쪽 문자열의 길이 값을 가지는 곳을 찾으면 된다.

코드

def getZarr(string, z):
    n = len(string)
    x, y, i = 0, 0, 0
    
    for k in range(1, n):
        if k > y:
            x, y = k, k
            while y < n and string[y-x] == string[y]:
                y += 1
            z[k] = y-x
            y -= 1
        else:
            i = k - x
            if z[i] < y-k+1:
                z[k] = z[i]
            else:
                x = k
                while y < n and string[y-x] == string[y]:
                    y += 1
                z[k] = y-x
                y -= 1
    
    return z

t = str(input())
p = str(input())
z = getZarr(p+"#"+t, [0] * (len(t)+len(p)+1))

results = []
count = 0
for i in range(len(p)+1, len(p)+len(t)+1):
    if z[i] == len(p):
        count += 1
        results.append(i - len(p))

print(count)
for i in range(len(results)):
    if i == len(results)-1:
        print(results[i])
    else:
        print(results[i], end=" ")