알고리즘 설계 실습 - KMP

---

문제

KMP 알고리즘을 구현하세요. 구현한 KMP 알고리즘으로 문자열 T에서 문자 열 P를 모두 찾고, 찾은 개수와 위치를 출력하세요.

첫째 줄에는 문자열 T가 주어집니다. 문자열 T의 길이 n은 1이상 100만 이하입니다. 둘째 줄에는 문자열 P가 주어집니다. 문자열 P의 길이 m은 1 이상 26 이하입니다. 문자열은 모두 알파벳 대문 자로만 이루어져 있습니다. (줄 바꿈 문자 \n을 포함하면 최대 문자열 길이가 2 추가됩니다.)

첫째 줄에는 문자열 T에서 문자열 P가 몇 번 나타나는지를 나타내는 음이 아닌 정수를 출력하세요. 둘째 줄에는 문자열 T에서 문자열 P가 나타나는 위치를 차례대로 공백으로 구분하여 출력하세요. 예를 들면, 문자열 T의 i～i+m-1번째 문자와 P의 1～m번째 문자가 차례로 일치한다면, i를 출력합니다. (여기서 i의 최솟값은 1입니다.)

---

KMP.py

# T(텍스트)와 P(패턴) 입력
T = input()
P = input()

def pattern():
    # next 배열을 생성 (배열은 부분 일치 테이블로 사용)
    next = [0 for i in range(0, len(P))]
    j = 0  # 패턴의 인덱스를 추적

    # 패턴 P의 각 문자에 대해 반복
    for i in range(1, len(P)):
        # j > 0이고 현재 패턴 문자가 일치하지 않는 동안
        # next 배열을 사용하여 j 인덱스를 갱신
        while j > 0 and P[i] != P[j]:
            j = next[j - 1]
        # 현재 패턴 문자가 일치
        if P[i] == P[j]:
            j += 1
            next[i] = j
    return next

def matching(next):
    ans = []  # 일치하는 시작 위치를 저장하는 리스트
    count = 0  # 일치하는 횟수
    j = 0  # 패턴의 인덱스

    # 텍스트 T의 각 문자에 대해 반복
    for i in range(0, len(T)):
        # j > 0이고 현재 텍스트 문자가 일치하지 않는 동안
        # next 배열을 사용하여 j 인덱스를 갱신
        while j > 0 and T[i] != P[j]:
            j = next[j - 1]
        # 현재 텍스트 문자가 패턴 문자와 일치하면
        if T[i] == P[j]:
            # 패턴의 끝에 도달했다면, 일치하는 위치를 ans에 추가
            if j == (len(P) - 1):
                ans.append(i - len(P) + 2)
                count += 1
                j = next[j]  # 다음 가능한 일치 시작점으로 j를 갱신
            else:
                j += 1
    # 일치하는 횟수와 위치를 출력
    print(count)
    print(*ans)

matching(pattern())

---