문자열을 검색하는 문제를 해결하려고 한다. LPS와 KMP 알고리즘에 대해서 알아보자.
문제
'soo'가 'yunsoowoo'의 부분 문자열인지 알고 싶다면?
나이브하게 한 문자씩 대조해가며 알아보는 방법이 있다.
하지만 원본 문자열 yunsoo의 길이가 N이고 탐색 문자열 soo의 길이가 M일 때 시간복잡도가 최악의 경우 $O(NM)$으로 비효율적이다.
LPS(Longest Prefix Suffix)
접두사(Prefix)와 접미사(Suffix)
LPS 를 위해서는 문자열 맨앞에 있는 접두사와 맨뒤에 있는 접미사가 같은 경우를 먼저 찾아야 한다!
아래 문자열에서 서로 일치하는 접두사와 접미사를 찾아보자.
'AB'라는 문자열이 앞과 뒤에서 반복되는 것을 볼 수 있다.
LPS는 서로 동일한 접두사와 접미사가 가장 긴 길이를 가리킨다.
파이 배열
이제 위 문자열 'ABAAB'에서, 인덱스별로 부분 문자열을 만들어가며 살펴보려고 한다. 첫 인덱스부터 부분 문자열을 만들어갈 것이다.
아래 그림을 참고하자.
인덱스별로 생성된 부분문자열마다 LPS, 즉 동일한 접두사-접미사의 최대 길이를 찾아볼 것이다.
이를 정리하여 배열로 나타내보자.
LPS = [0, 0, 1, 1, 2]
위를 파이(Pi) 배열이라고 부르기도 한다.
예제를 하나 더 가져와봤다. 'ABCABDAB'의 LPS 배열을 만들어보자.
| index | pattern | LPS[index] |
| 0 | ABCABDAB | 0 |
| 1 | ABCABDAB | 0 |
| 2 | ABCABDAB | 0 |
| 3 | ABCABDAB | 1 |
| 4 | ABCABDAB | 2 |
| 5 | ABCABDAB | 0 |
| 6 | ABCABDAB | 1 |
| 7 | ABCABDAB | 2 |
따라서,
LPS = [0, 0, 0, 1, 2, 0, 1, 2]
여기서 살펴볼 수 있는 점은, 이전 인덱스의 LPS값을 활용해서 현재 인덱스의 LPS값을 계산할 수 있다는 것이다.
위에서 본 pat = ABCABDAB 를 예시로 보겠다. 표와 함께 보면 좀더 이해가 쉬울 것이다.
idx == 3일 때 ABCABDAB 로 LPS=1이었다. 즉 동일한 접두사-접미사가 A로 최장 길이가 1이었다.
그 다음 인덱스는 idx == 4 일 때 부분 문자열은 ABCABDAB 이다.
이때 이전 LPS값이 1이므로, 맨 앞 글자 1개와 (B가 추가 되기 전) 맨 뒤 글자 1개가 이미 일치하는 상태다. 즉, pat[0] == pat[3] 이다.
따라서 idx==4의 LPS를 구할 때, 이전 LPS에서 확인된 것은 생략하고 그 다음 문자만 비교하면 된다. 앞 문자가 1개씩 일치하는 것은 이미 확인되었기 때문이다.
즉, pat[1]과 pat[4]만 검사해보면 된다.
검사 결과 pat[1] == pat[4] 이므로 이전 LPS값에 1을 더해 2가 된다.
idx == 4 와 idx == 5를 예시로 다시 살펴보겠다. lps = [0, 0, 0, 1, 2, ?] 에서 물음표를 구하려고 하는 것이다.
idx == 4 일 때 LPS 값이 2였다. 즉, pat[1]==pat[4]. 따라서 pat[2]와 pat[5]를 검사한다. 일치하지 않는다!!
그러면 이제 pat[5]와 무엇을 비교하면 될까? 한 칸 뒤로 가서, 그곳의 lps를 기준으로 다시 검사하면 된다.
한 칸 뒤로 물러나 1번 인덱스(B)로 가서, 그곳의 lps값(0)을 기준으로 다시 검사한다면?
lps가 0이므로 처음부터 검사한다고 보면 된다. 즉, pat[0]과 pat[5]를 검사한다. 같지 않으므로 lps 는 0이다.
이 과정이 왜 필요할까? ABCABD 가 아니라 ABCABA 였다고 생각해보자.
idx == 4 일 때 LPS 값이 2이고 pat[2]와 pat[5]를 검사했을 때 일치하지 않는 것까지는 위와 동일하다.
하지만 한칸 물러나, 그곳의 LPS값을 기준으로 다시 검사했을 때 위와 다르게 pat[0]와 pat[5]가 일치하는 것을 볼 수 있다.
코드로 자세히 살펴보자.
파이썬 코드
개인적으로 LPS 개념 자체는 괜찮았는데, 구현된 코드를 이해하는 게 조금 힘들었다. 화이팅.
pat = 'ABAAB'
M = len(pat)
lps = [0]*M # 부분문자열의 길이 M만큼 lps 리스트를 0으로 채워 초기화
def computeLPS(pat, lps):
leng = 0 # length of the previous longest prefix suffix
# 항상 lps[0]==0이므로 while문은 i==1부터 시작한다.
i = 1
while i < len(pat):
# 이전 인덱스에서 같았다면 다음 인덱스만 비교하면 된다.
if pat[i] == pat[leng]:
leng += 1
lps[i] = leng
i += 1
else:
# 일치하지 않는 경우
if leng != 0:
# 이전 인덱스에서는 같았으므로 leng을 줄여서 다시 검사
leng = lps[leng-1]
# 다시 검사해야 하므로 i는 증가하지 않음
else:
# 이전 인덱스에서도 같지 않았다면 lps[i]는 0 이고 i는 1 증가
lps[i] = 0
i += 1(출처 https://devbull.xyz/python-kmp-algorijeumeuro-munjayeol-cajgi/)
패턴 'ABAAB'를 예시로 코드를 살펴보자.
- lps = [0, 0, 0, 0, 0] : LPS 리스트를 0으로 초기화한다. 이때 리스트의 길이는 패턴의 길이와 같게 함.
- leng은 이전 인덱스의 접두사-접미사의 길이를 가리킨다. 앞으로 lps 리스트를 leng으로 업데이트할 것이다. (위에서 이전 LPS 값을 활용해 현재 LPS 값을 구한다고 설명했다)
- i는 인덱스를 가리킨다.
- 첫번째 인덱스(i==0)까지는 leng이 항상 0이다. 즉, lps[0] = 0 이다.
--> leng을 0으로 초기화하고 인덱스 i를 1부터 시작한다.
- while i < len(pat) : 패턴의 길이까지만 인덱스를 더해주며 while문 반복할 것이다. (당연함. 인덱스가 패턴의 길이를 벗어나선 안 됨.)
아래는 반복문에서 수행되는 내용을 표로 표현한 것이다.
| 반복문 시작 | |||
| ABAAB | i == 1 | [0, ?, ?, ?, ?] | - pat[1]과 pat[0]을 비교한다. 각각 B와 A이므로 일치하지 않아 else문으로 간다. - 이전 lps값인 leng이 0인지 검사한다. 0이므로 else문으로 간다. lps[1] = 0 으로 세팅하고 다음 인덱스로 간다. |
| ABAAB | i == 2 | [0, 0, ?, ?, ?] | - pat[2]와 pat[0]을 비교한다. 둘다 A로 일치하므로 if문으로 간다. - leng에 1을 더해 lps[2]=1 로 세팅하고 다음 인덱스로 간다. |
| ABAAB | i == 3 | [0, 0, 1, ?, ?] | - pat[3]와 pat[1]을 비교한다. 각각 A와 B이므로 일치하지 않아 else문으로 간다. - 이전 lps값인 leng이 0인지 검사한다. 0이 아니므로 if문으로 간다. - leng을 lps[0], 즉 0으로 세팅하고, 같은 인덱스에서 다시 검사한다. |
| ABAAB | i == 3 | [0, 0, 1, ?, ?] | - pat[3]과 pat[0]을 비교한다. 둘다 A로 일치하므로 if문으로 간다. - leng에 1을 더해 lps[3]=1 로 세팅하고 다음 인덱스로 간다. |
| ABAAB | i == 4 | [0, 0, 1, 1, ?] | - pat[4]과 pat[1]을 비교한다. 둘다 B로 일치하므로 if문으로 간다. - leng에 1을 더해 lps[4]=2 로 세팅하고 다음 인덱스로 간다. |
| [0, 0, 1, 1, 2] - 반복문 종료 | |||
[정리하자면]
(1) 이전 LPS값인 leng을 기준으로 현재 인덱스 i의 문자 pat[i]와 비교한다.
ex) 이전 LPS값이 0이라면, 이전에 일치한 접두사-접미사가 없다는 의미이므로 처음 문자부터 새로 비교한다. pat[0]과 pat[i] 비교.
ex1) 이전 LPS값이 1이라면, 이전에 일치한 접두사-접미사가 최대 길이 1이라는 의미이므로 그 다음 문자부터 비교한다. pat[1]과 pat[i] 비교 <-- 첫번째 문자 pat[0]까지는 일치한다는 거 이미 확인했다는 뜻이므로!!
ex2) 이전 LPS값이 2라면 이전에 일치한 접두사-접미사가 최대 길이 2이라는 의미이므로 그 다음 문자부터 비교한다. pat[2]과 pat[i] 비교 <-- 두번째 문자 pat[1]까지는 일치한다는 거 이미 확인했다는 뜻이므로!!
...
(2) 만약 일치한다면, 이전 LPS값에 길이 하나를 추가하고(앞에서 일치했던 접두사-접미사가 연장되었다는 의미), 다음 인덱스로 넘어간다
(개인적으로 이 부분이 제일 헷갈렸는데)
(3) 일치하지 않는다면, 이전 LPS값인 leng이 0인지 아닌지 검사한다
(3-1) 이전 LPS값이 0이라면, 이전에 일치한 접두사-접미사가 없다는 의미이므로 현재 LPS값을 0으로 설정하고 다음 인덱스로 넘어간다.
(3-2) 이전 LPS값이 0이 아니라면, 이전에 일치한 접두사-접미사가 있다는 의미이므로 그 이전 LPS값을 기준으로 다시 검사한다.
*나름의 팁..
LPS값의 변수명을 leng이라고 해서 괜히 더 헷갈리는데, '접두사가 끝나는 문자 다음의 인덱스'라고 생각하면 좀더 이해가 쉬울 수도 있다.
KMP 알고리즘
KMP는 Knuth, Morris, Prett이라는 세 명의 개발자 이름에서 따온 명칭이다.
앞서 LPS값, 즉 pi배열을 구했다. KMP 알고리즘은 LPS값을 이용해서 불필요한 검사를 건너뛴다.
동작 과정
원본 문자열 'ABCDABCDABE' 에서 주어진 패턴 'ABCDABE'가 부분 문자열인지 확인하려고 한다.
일단 갖다대고 문자를 하나씩 비교해본다.
운이 좋아서 'ABCDAB'까지는 일치했다. 그런데 마지막 문자 E가 일치하지 않았다.
우리는 'ABCDAB'까지, 즉 인덱스가 5일 때까지는 일치했다는 사실을 알고 있다. 이 사실과 LPS 값을 활용해서 불필요한 계산을 피해보자.
주어진 패턴의 LPS값을 구한다. 인덱스 5에서 LPS 값은 2이다. 즉, 앞의 두 문자가 뒤의 두 문자와 일치한다는 의미다. (아래 그림 참고)
그럼 뒷 AB 자리에 앞 AB가 오도록 패턴을 오른쪽으로 끌어당길 수 있다.
새로 위치한 상태에서 다시 비교해보면 된다. 이때, 첫 'AB'가 일치하는 건 알고 있으니, C부터 비교하면 된다.
시간복잡도
$O(M + N)$
파이썬 코드
def KMPSearch(pat, txt):
M = len(pat)
N = len(txt)
lps = [0]*M
# Preprocess the pattern
computeLPS(pat, lps)
i = 0 # index for txt[]
j = 0 # index for pat[]
while i < N:
# 문자열이 같은 경우 양쪽 인덱스를 모두 증가시킴
if pat[j] == txt[i]:
i += 1
j += 1
# Pattern을 찾지 못한 경우
elif pat[j] != txt[i]:
# j!=0인 경우는 짧은 lps에 대해 재검사
if j != 0:
j = lps[j-1]
# j==0이면 일치하는 부분이 없으므로 인덱스 증가
else:
i += 1
# Pattern을 찾은 경우
if j == M:
print("Found pattern at index " + str(i-j))
# 이전 인덱스의 lps값을 참조하여 계속 검색
j = lps[j-1]- N은 원본 문자열의, M은 패턴 문자열의 길이다.
- 주어진 패턴의 LPS 배열을 계산해둔다.
- 원본 문자열을 가리킬 인덱스 i와 패턴 문자열을 가리킬 인덱스 j를 0으로 초기화한다.
- i가 원본 문자열의 길이가 될 때까지 반복한다.
- i의 문자와 j의 문자가 일치하면 둘다 +1 하여 오른쪽으로 이동
- 일치하지 않는다면
- j가 0일 경우, i만 +1 하여 오른쪽으로 이동 (패턴의 첫번째 문자와 원본의 두번째 문자를 비교하기 위해서)
- j가 0이 아닐 경우 (앞에까지는 일치했기 때문에) j-1 의 lps 값 자리에 j를 둔다
- j가 주어진 패턴의 끝에 다다르면 부분 문자열로 일치한다고 판단, 계속 패턴을 찾기 위해 j-1 의 lps 값 자리에 j를 다시 둔다
j가 패턴 인덱스의 6자리에 있다가 2로 가는 부분을 꼭 제대로 살펴보기!!
예제
백준 예제로 KMP 알고리즘을 활용해보자.
https://woo-niverse.tistory.com/232
[백준/약점체크] 16916번: 부분문자열
[문제] 링크: https://www.acmicpc.net/problem/16916 [내 코드] 문제를 해결하기 위해서 KMP 알고리즘을 공부하고 구현했다. 자세한 내용은 이 글을 참고. def LPS(pat, lps): leng = 0 i = 1 while i < len(pat..
woo-niverse.tistory.com
'컴퓨터 > 알고리즘&자료구조' 카테고리의 다른 글
| 그래프 탐색 : BFS(너비 우선 탐색) (1) | 2022.10.07 |
|---|---|
| 그래프 탐색 : DFS(깊이 우선 탐색) (4) | 2022.10.07 |
| 최소 신장 트리 구하기 : 프림(Prim's) 알고리즘 (0) | 2022.10.05 |
| 최소 신장 트리 구하기 : 크루스칼(Kruskal) 알고리즘 (0) | 2022.10.05 |
| 합집합 찾기(union-find) (0) | 2022.10.05 |