[백준 1786] 찾기

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

1786번: 찾기

---

접근

문자열 패턴을 찾는 알고리즘인 KMP를 공부하기위해 위의 문제를 풀었다.

일단 지금까지 KMP 알고리즘을 다음과같이 이해했다.

문자열 S에서 패턴 문자 P를 찾는다고 하자. 이를 S의 처음부터 탐색하고 다른 문자가 나왔을 때 다시 P의 처음부터 탐색을 하면 불필요한 중복이 발생한다. 

따라서 P에서 각 인덱스까지의 문자까지 (ABCD가 있을 때 A, AB, ABC, ABCD) 최대 접미사, 접두사를 구한다. 이를 활용하여 S에서 P를 찾을 때 다른 문자가 나올 경우 다시 처음부터 돌아가는 것이 아니라 이전에 같은 위치까지의 정보를 활용하는 것이다.

 

아직까지 완벽히 이해한 것은 아니지만 어떠한 로직으로 구현해야하는지 알 수 있었고 앞으로 문제를 풀면서 더 명확하게 개념을 잡아가야겠다.

 

구현

- 먼저 패턴 문자열에서 최대 접미사, 접두사 길이를 구한다.

- 해당 길이를 0으로 초기화된 리스트에 넣는다.

- ABCAB가 있을 때 AB는 0, ABC도 0, ABCA는 1, ABCAB는 2가 되는 것이다.

def make_table(p):
    global table

    j = 0
    for i in range(1, len(p)):
        while j > 0 and p[i] != p[j]:
            j = table[j-1]

        if p[i] == p[j]:
            j += 1
            table[i] = j

- 이제 위에서 만든 테이블을 통해 문자열 내에 패턴 문자가 있는지 확인한다.

- 문자열의 문자와 패턴 문자의 문자가 같을 경우 j를 증가시킨다. 이는 패턴 문자의 인덱스다.

- 이때 j가 패턴 문자 길이 - 1이 된다면 패턴 문자가 존재하는 것으로 체크한다.

- 이제 문자가 다를 경우는 처음부터 다시 조사하는 것이 아니라 어디까지 맞았는지를 통해 j를 돌린다.

- 이를 통해 중복된 연산을 줄일 수 있다.

def kmp(t, p):
    answer = []
    j = 0
    for i in range(len(t)):
        while j > 0 and t[i] != p[j]:
            j = table[j-1]

        if t[i] == p[j]:
            if j == len(p) - 1:
                answer.append(i - len(p) + 2)
                j = table[j]
            else:
                j += 1
    return answer

---

전체 코드

def make_table(p):
    global table

    j = 0
    for i in range(1, len(p)):
        while j > 0 and p[i] != p[j]:
            j = table[j-1]

        if p[i] == p[j]:
            j += 1
            table[i] = j

def kmp(t, p):
    answer = []
    j = 0
    for i in range(len(t)):
        while j > 0 and t[i] != p[j]:
            j = table[j-1]

        if t[i] == p[j]:
            if j == len(p) - 1:
                answer.append(i - len(p) + 2)
                j = table[j]
            else:
                j += 1
    return answer

T = list(input())
P = list(input())

table = [0] * len(P)
make_table(P)
answer = kmp(T, P)
print(len(answer))
print(*answer)