string.md

문자열 처리 알고리즘

작성자 : 서그림

Table of Contents

• KMP 알고리즘 (Knuth-Morris-Pratt Algorithm)

---

문자열 패턴 매칭

문자열 T 안에 문자열 패턴 P가 존재하는지 찾아보자.

문자열 패턴 매칭에 완전탐색 알고리즘을 적용하면 문자열 T를 차례로 순회하면서 패턴 P 내의 문자들을 일일이 비교하게 된다. 이 때 최악의 경우 시간복잡도는 O(TP)를 가지므로, 매우 비효율적이다.

KMP 알고리즘 (Knuth-Morris-Pratt Algorithm)

완전탐색 알고리즘에서 '활용하지 못하는 정보'는 패턴이 안 맞다고 결론내기 전 '어디까지의 문자열이 일치했는지'에 대한 정보이다. KMP 알고리즘은 이 정보를 활용한다. 따라서 불일치가 발생하기 전의 문자열에 대하여 다시 비교하지 않고 매칭을 수행한다. O(T+P) 의 시간복잡도를 가지는 효율적인 알고리즘이다.

알고리즘 설계 및 구현

1. 패턴 P에 대하여 fail[k]를 구한다. (fail[k] : k 인덱스에서 접두사와 접미사가 일치하는 최대 길이)
2. 문자열 T는 인덱스 i로, 패턴 P는 인덱스 j로 차례로 순회하며 각 문자들을 비교한다.
3. j 인덱스에서 문자열 불일치가 발생하면 j 값을 fail[j-1] 값으로 설정하고 다시 비교를 수행해나간다. (j가 0이 되면 멈춤)

실패함수 fail 만들기

fail 함수는 패턴 매칭이 실패했을 때 패턴 포인터가 돌아갈 곳에 대한 정보를 관리한다. (전처리)

1. 0 인덱스는 돌아갈 곳이 없으므로 fail[0] = 0;
2. 패턴 P에 대하여 접미사는 인덱스 i로, 접두사는 인덱스 j로 차례로 순회하며 각 문자들을 비교한다. 3-1. i 인덱스와 j 인덱스의 문자열이 일치하면 fail[i] = ++j; 3-2. j 인덱스에서 문자열 불일치가 발생하면 j 값을 fail[j-1] 값으로 설정하고 다시 비교를 수행해나간다. (j가 0이 되면 멈춤)

KMP 알고리즘 구현 ▶️ KMPTest.java