알고리즘
[JAVA] KMP 알고리즘(문자열 검색)
clichy12
2019. 5. 13. 20:26
문자열 검색을 하는 가장 기본적인 방법은 pattern(len : M) 문자열을 target(len : N) 문자열 각 인덱스마다 각각 하나씩 확인하는 방법이다. 이 경우 시간복잡도는 N(NM)이 된다.
하지만 KMP 알고리즘을 이용하면 시간 복잡도 O(N+M)으로 엄청나게 효율적으로 문자열을 찾을 수 있다고 한다.
import java.util.Arrays;
class KMP {
static int[] makeTable(char[] p) {
int psize = p.length;
int[] table = new int[psize];
int j = 0;
for (int i = 1; i < psize; i++) {
while (j > 0 && p[i] != p[j]) {
j = table[j - 1];
}
if (p[i] == p[j]) {
table[i] = ++j;
}
}
return table;
}
static void kmp(char[] parent, char[] pattern) {
int[] table = makeTable(pattern);
int parentSize = parent.length;
int patternSize = pattern.length;
int j = 0;
for (int i = 0; i < parentSize; i++) {
while (j > 0 && parent[i] != pattern[j]) {
j = table[j - 1];
}
if (parent[i] == pattern[j]) {
if (j == patternSize - 1) {
System.out.printf("%d. \n", i - patternSize + 1);
j = table[j];
} else {
j++;
}
}
}
}
public static void main(String[] args) {
char[] parent = "ababacabacaabacaaba".toCharArray();
char[] pattern = "abacaaba".toCharArray();
System.out.println("target : " + Arrays.toString(parent));
System.out.println("pattern : " + Arrays.toString(pattern));
kmp(parent, pattern);
}
}

https://blog.naver.com/ndb796/221240660061
30. KMP(Knuth-Morris-Pratt) 알고리즘
이번 시간에 다루게 될 알고리즘은 KMP 알고리즘으로 대표적인 문자열(String) 매칭 알고리즘입니다. ...
blog.naver.com
https://bowbowbow.tistory.com/6
KMP : 문자열 검색 알고리즘
문자열 검색이 뭐지? 워드프로세서를 사용할 때 찾기 기능을 사용한적 있을 겁니다. 브라우저에서도 Ctrl+F 단축키를 눌러 검색할 수 있습니다. 아래 이미지는 브라우저에서 "테이프"를 검색했을 때 결과를 캡쳐한..
bowbowbow.tistory.com