백준 1786번

접근 방식(알고리즘 분류)

• KMP

내 풀이

# 일치하는 부분 문자열의 최대 길이를 기록하는 테이블 생성
def make_table(s):
    table = [0 for _ in range(len(s))]
    j = 0
    for i in range(1, len(s)):
        #같을때까지 j를 뒤로 건너뛰면서 후퇴
        while j > 0 and s[j] != s[i]:
            j = table[j-1]
        #같아집면 table에 j+1값을 대입 --> i, j 둘다 1씩 증가
        if s[j] == s[i]:
            table[i] = j + 1
            j += 1

    return table


def KMP(origin, pattern):

    result = []
    table = make_table(pattern)
    j = 0
    for i in range(len(origin)):
        while j > 0 and origin[i] != pattern[j]:
            j = table[j-1]

        #패턴의 마지막 인자까지 검사를 했다 --> 패턴 발견
        if origin[i] == pattern[j]:
            if j == len(pattern) - 1:
                result.append(i-len(pattern)+2)
                #패턴 발견시 다음 검사할 위치를 지정 --> 굳이 확인할 필요 없는 부분을 건너뜀
                j = table[j]
            else:
                j += 1
    return result


_origin = input()
_pattern = input()

answer = KMP(_origin, _pattern)
print(len(answer))
for i in answer:
    print(i, end=" ")

풀이 설명

• 기본적인 KMP 구현문제였다.
• 이 문제를 라빈카프 알고리즘을 통해서 풀어 봤으나 시간 초과로 통과 하지 못했다.
• 문제의 유형에 따라 접근 방식을 달리해야 함을 느꼈다.