•
개요
◦
대표적인 문자열 검색 알고리즘이다.
◦
주요개념은 불일치가 발생하기 직전까지 같았던 부분은 다시 비교하지 않고 패턴 매칭을 진행하는 것이다.
◦
비교 횟수를 줄이고 검색 알고리즘의 효율성을 높이는 것이 이 알고리즘의 의도이다.
•
구현
◦
구현에 있어서 접두부와 접미부, 경계에 대한 의미를 알고 있어야 한다.
◦
접두부 배열은 문자열의 왼쪽부터 시작하여 한 개씩 읽어가면서 만들고, 접미부 배열은 문자열의 마지막부터 시작하여 마찬가지로 한 개씩 읽어가면서 만든다.
◦
경계는 접두부와 접미부가 같을 때, 그 접두부 또는 접미부를 경계라고 한다.
◦
목적 문자열과 비교 문자열의 일치하는 패턴을 발견했을때, 해당 패턴의 길이 - 해당 패턴의 길이에서 최대 경계 값만큼 이동시켜 탐색하는 것이다.
◦
그때 그때 구할 수 없으니 이는 이동경로 테이블을 만들어두고 사용한다.
•
코드
package string;
public class KMP {
public static void main(String[] args) {
String s = "abacabacabacaabacabaac";
String p = "abacabaac";
int[] pi = getPi(p);
int result = kmp(s, p, pi);
System.out.println(result);
}
public static int[] getPi(String p) {
// pi[i] : p[0] ~ p[i]까지의 부분 문자열 중에서 접두사 == 접미사의 최대 길이
int[] pi = new int[p.length() + 1];
pi[0] = -1;
// j : 접두사 == 접미사의 최대 길이
int j = 0;
// i : 접미사 포인터
for (int i = 1; i < p.length(); i++) {
// j가 0보다 크고, 접두사와 접미사가 다르면 j를 pi[j-1]로 갱신
while (j > 0 && p.charAt(i) != p.charAt(j)) {
j = pi[j];
}
// 접두사와 접미사가 같으면 j를 증가시키고 pi[i]에 j를 저장
if (p.charAt(i) == p.charAt(j)) {
pi[i + 1] = ++j;
}
}
return pi;
}
public static int kmp(String s, String p, int[] pi) {
int sLen = s.length();
int pLen = p.length();
int dist = 0;
int idx = 0;
int cnt = 0;
while (true) {
idx = 0;
if ((idx + dist) + pLen > sLen) {
break;
}
while (s.charAt(idx + dist) == p.charAt(cnt)) {
idx++;
cnt++;
if (cnt == pLen) {
return dist;
}
}
dist = dist + (cnt - pi[cnt]);
cnt = 0;
}
return 0;
}
}
Java
복사
