https://www.acmicpc.net/problem/1786
1786번: 찾기
첫째 줄에, T 중간에 P가 몇 번 나타나는지를 나타내는 음이 아닌 정수를 출력한다. 둘째 줄에는 P가 나타나는 위치를 차례대로 공백으로 구분해 출력한다. 예컨대, T의 i～i+m-1번 문자와 P의 1～m
www.acmicpc.net
def kmp(all_string, pattern):
# kmp_table
table = [0 for _ in range(len(pattern))]
i = 0
for j in range(1, len(pattern)):
while i > 0 and pattern[i] != pattern[j]:
i = table[i-1]
if pattern[i] == pattern[j]:
i += 1
table[j] = i
# kmp
result = []
i = 0
for j in range(len(all_string)):
while i > 0 and pattern[i] != all_string[j]:
i = table[i-1]
if pattern[i] == all_string[j]:
i += 1
if i == len(pattern):
result.append(j - i + 1 + 1)
i = table[i-1]
return result
a = input()
b = input()
result = kmp(a, b)
print(len(result))
print(*result)KMP 그 자체인 문제다.
댓글