BOJ - 1786번 찾기

출처 - 백준 1786번

KMP 알고리즘을 복습해보고자 새로운 문제를 풀다가 😮 생각못했던 반례에서 잘못된 input으로 계속 파라미터를 받아서 틀리고 있었다는 것을 깨닫고 포스팅한다..

알고리즘은 전반적으로 KMP를 사용하는데 문제에서도 주어지듯이 문제 설명을 보면 KMP알고리즘에 대한 설명이다. 그래서 전에 문제와 동일하게 KMP알고리즘에 사용되는 pi 테이블을 생성해주었고 주어진 문자열 내에서 패턴이 몇번 나오는지 검사를 해야했기 때문에 result란 배열에 결과를 저장해주었다.

🎯 소스코드

T = input()
P = input()


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


def KMP(parent, pattern):
    result = []
    tb = create_table(pattern)
    j = 0
    for i in range(len(parent)):
        while j > 0 and pattern[j] != parent[i]:
            j = tb[j - 1]
        if pattern[j] == parent[i]:
            if j == len(pattern) - 1:
                result.append(i - len(pattern) + 2)
                j = tb[j]
            else:
                j += 1
    return str(len(result)) + '\n' + ''.join([str(e) + ' ' for e in result])

print(KMP(T, P))

😭 겪었던 issue

수정하기 전 소스코드는 입력을 습관적으로

import sys

T = sys.stdin.readline().strip()
P = sys.stdin.readline().strip()

이렇게 받았었는데 이게 문제가 됐다. readline()으로 한줄을 모두 읽은 다음에 strip을 해주는 바람에 양옆에 공백이 사라지게 된다.

하지만! 만약에 패턴이 공백으로 이루어졌다면 절대 답을 도출해낼 수 없다!

그래서 모두 input()으로 바꿔주었다.

반례 모음

dltmdals0608 님의 반례

# 패턴이 띄어쓰기로만 이루어진 경우
ab  ab
  # 띄어쓰기 2개
답 : 
1
3

banana banana
ana
답 :
4
2 4 9 11

저는 이 두개로 해서 모두 성공했습니다 😀

찾아보다가 좋은 글이 있길래 퍼왔습니다.
dbfldkfdbgml 님의 반례
https://www.acmicpc.net/board/view/52492