반응형
문자열 패턴 매칭
라빈-카프 알고리즘
- 문자열 검색을 위해 해시 값 함수와 슬라이딩 윈도우 기법을 사용
- 문자열을 mod 연산을 통해 해쉬값 취환
- 문자를 일일이 비교하지만 해시를 사용하므로 최악은 O(MN) 이지만 선형적일수록 효율적이다. (단, 해쉬 충돌 여지가 있다.)
보이어 무어 알고리즘
- 문자열을 오른쪽에서 왼쪽으로 비교
- 끝 문자가 비교 문자랑 다르다면 끝 문자가 패턴에 포함되어 있는지 확인하고, 있다면 그 길이만큼 이동, 없다면 패턴의 길이 만큼 이동
- 최악은 O(MN) 이지만 최선은 O(N/M)이며 평균적으로 높은 속도를 가지는 알고리즘
skip 배열
- skip 횟수를 저장한 배열 - 뒤로 갈 수 있는 거리 만큼 배열에 저장
- 패턴이 "rithm" 이라면 패턴의 길이는 5이다. a~z 중 r =4, i=3, t=2, h=1, m=5 나머지 는 5가 된다.
KMP 알고리즘
- KMP는 알고리즘을 설계한 Knuth-Morris-Pratt의 앞글자를 하나씩 따서 만든 알고리즘으로 문자열 검색을 효율적으로 할 수 있는 알고리즘이다. (ctrl + f 해서 찾는 검색 알고리즘이 KMP 알고리즘)
- 전체 텍스트의 길이를 N, 찾고자하는 문자열을 M이라 할 때 각 인덱스 별 비교를 하면 시간 복잡도는 O(NM)이지만, KMP 알고리즘을 적용하면 O(N+M)으로 찾을 수 있다.
실패 함수
- KMP 알고리즘의 원리는 실패함수를 이용하는 것이다. 실패 함수란 문자 매칭에 실패했을 때 전체 비교인 O(NM)을 효율적으로 처리하기 위해 건너 뛸 자리를 구하기 위한 함수이다. 즉, 텍스트와 패턴이 불일치 상황에서 접두사 / 접미사가 일치한 최대 길이를 구하여 다음에 건너 뛸 자리를 결정하는 것이다.
전체 문자열이 "ABCCBAABBA" 일 때, 가장 긴 부분 문자열과 그 길이를 담을 실패함수 배열 pi
- 실패 함수를 사용하기 위해선 접두사(prefix)와 접미사(suffix)를 사용하여 prefix == suffix가 될 수 있는 가장 긴 부분 문자열을 배열에 담아야 한다.
- 가장 긴 부분 문자열을 왜 쓸까? 예시로 보자. ABCDABCDABEF 라는 텍스트에서 ABCDABE를 찾는다고 생각해보자. 처음 시작 인덱스를 맞추어서 비교했을 때 각 6번 인덱스가 C,E로 서로 다르기 때문에 원하는 패턴이 아니다. 즉, 실패를 한 상황이다. 이 때 pi[]배열에 가장 긴 부분 문자열을 채운다.
- 중간 단계를 건너 뛰고 현재 단계로 넘어갈 수 있다. i는 텍스트의 현재 비교 위치, j는 패턴의 현재 비교위치를 나타내는 변수로 ABCDAB에서 최대 부분 문자열의 길이는 "AB"인 2(pi[5])이다. 즉, 다음에 비교할 대상은 인덱스4부터 시작이다. 하지만 이미 구해둔 최대 길이는 2 이므로, i와 j는 4에 둘 필요 없이 4 + 2인 6인덱스에 두고 비교를 한다.
- i = 5 일 때를 보자. j = 3 에서 문자열 매칭이 실패한다. 이 경우 pi[3-1]만큼 j의 인덱스부터 현재의 i값이랑 비교한다. pi[2]는 1이므로 j=1 인덱스로 비교해봤지만 해당 인덱스도 다르고 0 또한 마찬가지로 다르다.
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String text = br.readLine();
String pattern = br.readLine();
kmp(text, pattern);
}
private static void kmp(String text, String pattern) {
int[] pi = getPi(pattern);
int j = 0;
for (int i = 0; i < text.length(); i++) {
// text 인덱스와 pattern 인덱스가 다르다면 마지막에 성공한 실패함수 인덱스 값으로 이동
while (j > 0 && text.charAt(i) != pattern.charAt(j)) j = pi[j-1];
if (text.charAt(i) == pattern.charAt(j)) {
// 패턴이 텍스트에 속해 있다면
if (j == pattern.length()-1) {
return;
}
else j++;
}
}
}
private static int[] getPi(String word) {
int[] pi = new int[word.length()];
int j = 0;
for (int i = 1; i < word.length(); i++) {
while (j > 0 && word.charAt(i) != word.charAt(j)) {
j = pi[j-1];
}
if (word.charAt(i) == word.charAt(j)) pi[i] = ++j;
}
return pi;
}
}반응형
