1786번: 찾기 / platinum 5 / KMP

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

1786번: 찾기

 

- 틀렸습니다 

'''
1786번: 찾기 / platinum 5 / 
'''
# T, P 문자열 입력
T = input()
P = input()

t_len = len(T)
p_len = len(P)
p_index = 0
p2_index = 0
same_index = []
# T 문자열 하나씩 보기
for t_index in range(t_len):
    # T와 P가 같을시,
    if T[t_index] == P[p_index]:
        # p_index 1 증가
        p_index += 1
        # P 문자열 끝까지 같다면 초기화
        if p_index == p_len:
            same_index.append(t_index + 1 - p_len + 1)
            p_index = 0
            p2_index = 0
            continue
        # p 인덱스 2번 이후 값과 비교한 거라면
        if p_index >= 2:
            # 값이 같으면 p2_index 생성
            if T[t_index] == P[p2_index]:
                p2_index += 1
            else:
                p2_index = 0
    # T와 P가 다를시,
    else:
        # p2_index 있을 시, p_index로 전환
        if p2_index != 0:
            p_index = p2_index
            p2_index = 0
        else:
            p_index = 0

print(len(same_index))
for i in same_index:
    print(i, end=' ')

'''
1786번: 찾기 / platinum 5 / 
'''

# T, P 문자열 입력
T = input()
P = input()

t_len = len(T)
p_len = len(P)
p_pointer = [0, 0]
same_index = []
# T 문자열 하나씩 보기
for t_index in range(t_len):
    # T와 P가 같을시,
    if T[t_index] == P[p_pointer[0]]:
        p_pointer[0] += 1
        # P 문자열 끝까지 같다면 초기화
        if p_pointer[0] == p_len:
            same_index.append(t_index + 1 - p_len + 1)
            p_pointer = [0, 0]
            continue
        #
        if p_pointer[0] >= 2:
            i = 1
            while i != len(p_pointer):
                if T[t_index] == P[p_pointer[i]]:
                    p_pointer[i] += 1
                    i += 1
                else:
                    p_pointer.pop(i)
            p_pointer.append(0)
    # T와 P가 다를시,
    else:
        p_pointer.pop(0)
        i = 0
        while i != len(p_pointer):
            if T[t_index] == P[p_pointer[i]]:
                p_pointer[i] += 1
                i += 1
            else:
                p_pointer.pop(i)
        p_pointer.append(0)

# 출력하기
print(len(same_index))
for i in same_index:
    print(i, end=' ')

 

 

- 정답 코드

'''
1786번: 찾기 / platinum 5 / KMP(Knuth-Morris-Pratt)
'''
# T, P 문자열 입력
T = input()
P = input()

# pi 리스트 만들기
pi = [0 for _ in range(len(P))]
pointer = 0
for i in range(1, len(P)):
    while pointer > 0 and P[i] != P[pointer]:
        pointer = pi[pointer - 1]
    if P[i] == P[pointer]:
        pointer += 1
        pi[i] = pointer

# same_cnt, same_index 구하기
same_cnt = 0
same_index = []
pointer = 0
# T 문자열 하나씩 확인하기
for i in range(len(T)):
    # T와 P 문자열 비교 중, 다를 시 처리
    while pointer > 0 and T[i] != P[pointer]:
        pointer = pi[pointer - 1]
    # T와 P 문자열 비교 중, 같을시 처리
    if T[i] == P[pointer]:
        # P 문자열과 같은 문자열 발견
        if pointer == len(P) - 1:
            same_index.append(i - len(P) + 2)
            same_cnt += 1
            pointer = pi[pointer]
        # 아직 P 문자열 아님
        else:
            pointer += 1
# 출력하기
print(same_cnt)
for v in same_index:
    print(v)

코드 리뷰

- KMP 알고리즘을 모르는 상태에서 해당 문제를 풀었기에 첫 코드에서 틀림 판정을 받았습니다!

- 이런저런 삽질을 하다가 도저히 모르겠어서 구글링을 통해 KMP 알고리즘 방법을 알게 되었습니다.

 

KMP 알고리즘 이해

- 패턴 문자열에서 이미 일치한 부분을 이용하여 불필요한 비교를 줄이는 것이 특징

 

(1) pi 리스트 만들기

- 검색 할 문자열의 패턴을 확인하고 넣어주는 작업을 실행 합니다.

(2) same_cnt, same_index 구하기

# T 문자열 하나씩 확인하기

    # T와 P 문자열 비교 중, 다를 시 처리

    # T와 P 문자열 비교 중, 같을시 처리

        # P 문자열과 같은 문자열 발견 => same_cnt 1증가 / 발견한 문자열의 처음 인덱스 same_index에 추가

        # 아직 P 문자열 아님 => pointer 1증가

(3) same_cnt, same_index 출력하기