백준: 1786 찾기

문제

1786번: 찾기

 

문제 풀이

 문자열과 패턴이 주어지면, 이를 통해 몇 개가 일치하고 어느 위치에 일치하는지 반환하는 문제이다. 앞서 다룬 16916 부분 문자열과 같이 `KMP 알고리즘`을 이해하고 있으면 쉽게 해결할 수 있는 문제이다. 앞서 다룬 문제와 다른 점이 있다면 패턴과 일치하는 경우 바로 결과를 반환하지 않고, 값을 추가하여 모든 탐색이 끝난 후에 반환하는 부분을 수정하면 된다.

 

코드

def make_table():
    length = len(p)
    table = [0] * len(p)
    j = 0
    for i in range(1, length):
        while j > 0 and p[i] != p[j]:
            j = table[j - 1]
        if p[i] == p[j]:
            j += 1
            table[i] = j
    return table


def kmp():
    table = make_table()
    j = 0
    ret = []
    for i in range(len(s)):
        while j > 0 and s[i] != p[j]:
            j = table[j - 1]
        if s[i] == p[j]:
            if j == len(p) - 1:
                ret.append(i - len(p) + 2)
                j = table[j]
            else:
                j += 1
    return ret


if __name__ == "__main__":
    s = input()
    p = input()
    result = kmp()
    print(len(result))
    print(*result)