문제
문자열에 대해 원하는 패턴이 존재하면 패턴이 몇번 나타나는지 또 패턴이 나타나는 위치를 출력하는 문제이다.
풀이
KMP알고리즘을 활용하면 해결할 수 있다.
KMP알고리즘의 아이디어는 다음과 같다.
패턴에 대해 반복되는 부분이 있다면, 모든 문자열을 비교할 필요 없이 반복되는 부분은 건너뛸 수 있지 않을까?
그걸 구체적으로 구현하면 아래와 같이 된다.
먼저 패턴을 이용하여 Lps배열을 만든다.
Lis배열이란 패턴이 얼마나 중복된 패턴을 가지고 있는지 나타내는 배열이다.
abcdabc패턴에 대해서는 다음과 같이 lps배열이 만들어진다.
해당 과정을 코드로 나타내면 다음과 같다.
def makeLps(p): #Lps 배열을 만든 후 리턴
tmpTable = [0] * len(p)
j = 0
for i in range(1, len(p)):
while j > 0 and p[i] != p[j]:
j = tmpTable[j - 1]
if p[i] == p[j]:
j += 1
tmpTable[i] = j
return tmpTable
만든 Lps패턴은 위와같이 이용된다.
text의 i인덱스와 패턴의 j 인덱스를 비교하며 나아간다.
이 때 글자가 일치한다면 i와 j를 증가시켜 다음 글자를 비교하고
일치하지 않고, j가 0보다 크다면 즉 처음 비교가 아니라면, j 값을 lps테이블을 이용하여 점프해준다.
이렇게 하면 효율적으로 문자열을 찾을 수 있다.
def KMP(T, P):
result = []
cnt = 0
j = 0
for i in range(len(T)):
while j > 0 and T[i] != P[j]:
j = table[j - 1]
if T[i] == P[j]:
if j == len(P) - 1: #패턴과 모두 일치할 경우
cnt += 1
result.append(i - len(P) + 2)
j = table[j]
else:
j += 1
return cnt, result이를 코드로 표현하면 위와같아진다.
코드
def makeLps(p): #Lps 배열을 만든 후 리턴
tmpTable = [0] * len(p)
j = 0
for i in range(1, len(p)):
while j > 0 and p[i] != p[j]:
j = tmpTable[j - 1]
if p[i] == p[j]:
j += 1
tmpTable[i] = j
return tmpTable
def KMP(T, P):
result = []
cnt = 0
j = 0
for i in range(len(T)):
while j > 0 and T[i] != P[j]:
j = table[j - 1]
if T[i] == P[j]:
if j == len(P) - 1: #패턴과 모두 일치할 경우
cnt += 1
result.append(i - len(P) + 2)
j = table[j]
else:
j += 1
return cnt, result
T = input()
P = input()
table = makeLps(P)
a, b = KMP(T, P)
print(a)
print(*b)