문제 이해
문제 자체는 정말 단순하다. 긴 문자열이 쭉 주어지고, pattern이라는 짧은 문자열이 주어졌을 때 긴 문자열 안에서 pattern이 몇 번 반복되는지 찾는 문제이다.
하지만 단순한 문제에 그렇지 않은 설명 길이를 보면 어려운 문제임을 직감할 수 있다.
이 문제가 어려운 이유는 시간 복잡도 때문 일 것이다. 단순히 접근한다면 패턴 길이만큼을 패턴과 같은지 체크하면서 한 칸씩 전진하면 될 것이다. 물론 해결이 가능하지만 문제 설명에 쓰여 있는 것과 같이 시간 복잡도를 만족시킬 수 없다.
더 효율적인 코드가 필요하고, 이를 위한 대표적인 문자열 알고리즘으로는 Boyer-Moore, Rabin-Karp, KMP 등이 있다.
그 중에서 이번에는 KMP 알고리즘으로 문제를 해결해보자.
실제 코드
def failNaive(pattern): # 실패함수 주의해서 짜기
result = [0 for _ in range(len(pattern))]
i = 0
j = 1
while j < len(pattern):
if pattern[i] == pattern[j]:
i += 1
result[j] = i
j += 1
else:
if i != 0:
i = result[i - 1]
else:
result[j] = 0
j += 1
return result
def kmp(text, pattern):
result = []
posT = 0
posP = 0
f = failNaive(pattern)
while posT < len(text):
if text[posT] == pattern[posP]:
posT += 1
posP += 1
if posP == len(pattern):
result.append(posT - posP + 1)
posP = f[posP - 1] # 그냥 0으로 보내면 스킵하게 되는 부분 생김
else:
if posP == 0: # 왜 posT로 두면 안될까?
posT += 1
else:
posP = f[posP - 1]
return result
text = input()
pattern = input()
result = kmp(text, pattern)
print(len(result))
for i in result:
print(i, end=" ")
해설
KMP 알고리즘은 크게 두 가지 함수로 구성된다.
첫째는 흔히 실패함수 라고 불리고 두 번째는 kmp함수이다.
먼저 실패함수를 이해해야한다. 이전에 살펴본 브루트포스 한 방식의 풀이는 어떤 경우에도 한 문자씩 전진하며 패턴과의 일치 여부를 판단했다. 하지만 패턴 안에 중복되는 문자열이 있는 경우 이 전진하는 단위를 더욱 늘릴 수 있을 것이라는 아이디어가 생겨난 것이다. 이것이 KMP 알고리즘의 기반이다. 아래 그림을 보면 조금 이해가 편할 것 같다.
각 단계별로 위에 있는 것이 긴 문자열, 아래 있는 것이 pattern이다. 1번 단계에서 검사를 하다보니 마지막 문자만 자르고 모두 같은 것을 알 수 있다. 아쉽다는 생각에서 끝나면 안된다. 검사를 통해 우리에게 정보가 주어진 것이다. 블랙박스 같던 긴 문자열에 우리가 아는 값들이 생긴 것이다. 정보를 얻었으면 적절히 이용해야한다.
pattern을 보니 시작하는 부분의 AB와 중반부에 있는 AB가 반복이 일어나는 최대 문자열인 것을 알 수 있다 (그 사이에는 시작 부분과 겹치는 부분이 없다). 즉 긴 문자열을 만족시킨 부분 중, pattern의 접두사와 접미사를 확인하여 최대로 반복 가능한 구간을 찾아낸 것이다. 그렇게 하면 브루트포스처럼 한 칸 전진이 아니라, 한 번에 여러 칸을 전진시킬 수 있는 확실한 근거가 찾아지는 것이다.
그리고 이것을 가능하게 만들어주는 것이 pattern의 pattern을 찾는 알고리즘, 즉 실패함수를 만드는 것이다 (위의 그림에서는 pattern 아래에 적힌 숫자 표가 그것이다).
두 번째로 kmp 함수를 살펴보자. 이제는 pattern과 긴 문자열 각각의 인덱스를 비교하며 같은 구간을 찾는다.
이제 달랐을 때에 집중해야한다.
- pattern의 인덱스가 0번째였을 경우에는 긴 문자열만 하나 전진시키면 된다.
- pattern의 인덱스가 0번째가 아닌 경우는, 그냥 0으로 옮기는 것이 아닌 pattern의 반복 구간을 고려해서 최적의 위치로 posP를 이동시킨다. 즉 실패함수를 이용한다.
같은 경우에는 원래의 경우라면 pattern과 긴 문자열의 인덱스를 같이 전진시키면 된다. 하지만 이 문제의 특성상 몇 번 반복인지 찾는 것이기 때문에, 반복되는 것을 한 번 찾더라도 다시 다음 패턴을 찾을 준비를 해야한다.
- 이 부분이 가장 어려웠는데, 이때도 posP를 바로 0으로 가면 스킵하게 되는 부분이 생긴다. 따라서 실패함수를 이용해야한다.
실버 문제들도 힘겹게 풀던 시절 이 문제를 접했다. 무식하게 풀어보려 했던 것은 아니고 자료구조 수업 시간에 해당 알고리즘을 배우게 되면서 연습삼아 풀었던 것이다. 그때부터 지금까지 내가 풀었던 문제 중 아직까지는 가장 어려웠던 문제 같다. 당시에도 3시간을 고민하다가 종이에 직접 과정을 하나하나 써가면서 겨우 이해했던 것 같다. 하지만 일주일 정도 지났을까, 이해했던 부분을 놓쳐서 또 고생을 하였다. 부지런히 공부해야하는 이유를 깨닫게 해주는 문제였다.