고지식한 알고리즘
문자열을 처음부터 끝까지 차례대로 순회하면서 패턴 내의 문자들을 일일이 비교하는 방식
시간 복잡도 O(MN)
라빈-카프 알고리즘
- 문자열 검색을 위해 해시 값 함수를 이용
- 패턴 내의 문자들을 일일이 비교하는 대신 패턴의 해시 값과 본문 안에 있는 하위 문자열의 해시값만을 비교
- 최악의 시간 복잡도 O(MN), 평균적으로 선형에 가까운 빠른 속도 ,대략 O(M+N)
숫자 문자열 : 6843212431
찾으려는 패턴 : 4321
- 패턴의 해쉬값을 계산 -> 각 자리의 숫자에 자리값을 곱하여 더함 ("4321"은 정수 4321이 됨)
- 찾고자 하는 문자열에서 4자리씩 해쉬값을 계산 -> (6843, 8432...)
- 새로 추가되는 문자와 그전에 읽었던 값을 이용해서 해쉬값을 구함 ((6843 % 1000) * 10 + 2 = 8432)
- 처음 해쉬값을 구할때 찾고자 하는 문자열에서 패턴 길이만큼 읽어서 구한다.
- 예제는 패턴의 길이를 4자리 정수로 작게 했지만 패턴이 문자열이며 길이가 커지면 길이를 일정 자리수로 맞추기 위해 mod연산을 취한다.
- 해쉬값이 일치하더라도 실제 패턴이 일치하지 않을 수 있기때문에 해쉬값이 일치하면 문자열 일치를 검사해야 한다.
- ( 15 mod 10 -> 5, 25 mod 10 -> 5, 35 mod 10 -> 5 모두 해쉬값 동일)
보이어 무어 알고리즘
- 패턴에 오른쪽 끝에 있는 문자가 불일치하고 이 문자가 패턴 내에 존재하지 않는 경우, 같은 문자는 맞춰두고 점프.
- 최악의 시간 복잡도 O(NM), 최선의 시간복잡도 O(N / M), 평균적으로 가장 빠른 속도를 가지는 알고리즘
문자열 : aaaaabbbbbwater
찾으려는 패턴 : water
aaaaabbbbbwater
water 불일치 -> 3칸 점프 (문자열의 a와 패턴의 a를 맞춰 줌)
skip 배열
- skip[ch] : 본문 ch 문자에서 패턴 불일치가 발생했을때 본문포인터의 skip횟수
- 패턴에 포함되지 않은 문자들은 본문포인터가 패턴 길이만큼 skip 해야하므로 패턴의 길이가 skip 배열의 값이 됨.
- 패턴 문자들의 skip 배열값 (패턴 마지막 문자는 제외)
- (패턴문자열의 길이-1) - 각 패턴 문자의 인덱스
- rithm 패턴 문자열의 skip 배열
rithm
문자열에서 r을 만나면 4칸 skip
문자열에서 i를 만나면 3칸 skip
문자열에서 t를 만나면 2칸 skip
문자열에서 h를 만나면 1칸 skip
문자열 : a parttern matching algorithm
패턴 : rithm
- a parttern matching algorithm -> 2칸 skip
- a parttern matching algorithm -> 5칸 skip
- a parttern matching algorithm -> 5칸 skip
- a parttern matching algorithm -> 5칸 skip
- a parttern matching algorithm -> 5칸 skip
- a parttern matching algorithm -> 5칸 skip
- a parttern matching algorithm -> 일치
KMP 알고리즘
- 불일치가 발생한 텍스트 문자열의 앞 부분에 어떤 문자가 있는지를 미리 알고 있으므로 불일치가 발생한 앞 부분에 대하여 다시 비교하지 않고 매칭을 수행
- 패턴을 전처리하여 부분일치 테이블 배열 pi[k]을 구해서 잘못된 시작을 최소화함
- pi[k] : 처음부터 k인덱스까지를 끝으로 하는 부분 문자열에서 일치하는 접두사와 접미사가 일치하는 최대 길이
- 시간 복잡도는 O(M+N)
- 파란 부분 동일 -> 4칸 skip
pi 배열 생성
- 패턴을 이용하여 부분 일치 테이블 배열 작성
- 매칭이 실패했을 때 패턴 포인터가 돌아갈 곳을 계산
- 패턴의 0번째 인덱스를 제외한 각 인덱스마다 맨 앞부터 해당 인덱스까지의 부분 문자열 중 접두사와 접미사가 일치하는 최대 길이로 구함
예) ababaca
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
// KMP 알고리즘(Knuth–Morris–Pratt Algorithm)
// O(N+M)
public class String_KMPTest {
public static void main(String[] args) throws Exception {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
char[] text = in.readLine().toCharArray();
char[] pattern = in.readLine().toCharArray();
int tLength = text.length, pLength = pattern.length;
// 부분일치테이블 만들기 : KMP의 아이디어를 똑같이 적용, W에서 W를 찾는 듯한 행위를 해서...
int[] pi = new int[pLength];
for(int i=1, j=0; i<pLength; i++){// i:접미사 포인터(i=1부터 시작: 우리는 부분일치테이블를 만드는게 목적이므로 첫글자 틀리면 0위치로 가야하므로.), j:접두사 포인터
while(j > 0 && pattern[i] != pattern[j]) j = pi[j-1];
if(pattern[i] == pattern[j]) pi[i] = ++j;
else pi[i] = 0;
}
int cnt = 0;
ArrayList<Integer> list = new ArrayList<Integer>();
// i : 텍스트 포인터 , j: 패턴 포인터
for(int i=0,j=0; i<tLength; ++i) {
while(j>0 && text[i] != pattern[j]) j = pi[j-1];
if(text[i] == pattern[j]) { //두 글자 일치
if(j == pLength-1) { // j가 패턴의 마지막 인덱스라면
cnt++; // 카운트 증가
list.add((i+1)-pLength);
j=pi[j];
}else {
j++;
}
}
}
System.out.println(cnt);
if(cnt>0) {
System.out.println(list);
}
}
}
'코딩테스트 > [알고리즘] 알고리즘 정리' 카테고리의 다른 글
이진 탐색 알고리즘 (0) | 2021.10.07 |
---|---|
다이나믹 프로그래밍 (0) | 2021.10.05 |
그리디 알고리즘 (0) | 2021.10.04 |
백트래킹 알고리즘 (0) | 2021.10.03 |
그래프 탐색 알고리즘 - DFS / BFS (0) | 2021.10.02 |