1786 찾기
1. kmp 알고리즘
문자열 검색 알고리즘(kmp) 에 대해 먼저 자세하게 설명하겠다.
1) 예제
예를 들어 설명하겠다.
문자열 all : ABCDABCDABEF
문자열 part : ABCDABE
가 있을때,
all 에 part 문자열이 있는지 확인해보자.
문자열 all의 길이를 N, 문자열 part의 길이를 M이라고 했을 때,
한 글자씩 모두 비교하면,
시간복잡도는 O(N*M) 으로 매우 오래 걸리지만,
이 방법을 사용하면, O(N+M) 으로 짧아지게 된다.
2) value 배열
일단 value 배열을 만들 것이다.
이 배열은, 문자열 part의 0~i번째까지 부분 문자열 중 접두사와 접미사가 같은 최대 길이이다.
즉, 아래와 같다.
이 배열을 왜 만들었는지는 아래에서 좀 더 살펴보면 알 수 있을 것이다.
그러면 이제 문자열 all과 문자열 part를 비교해보자.
3) kmp 알고리즘 만들기
문자열 all의 인덱스는 i로,
문자열 part의 인덱스는 index로 해보자.
표에는 인덱스 i만 표시했다.
인덱스 i = 0, index = 0 부터 문자열 all과 part를 비교해보자.
그러면 0~5까지는 글자가 같지만,
6번째에서 글자가 다르다.
그러면 이제
문자열 part 를 문자열 all 의 몇 번째 부터 비교해야 되는지 살펴보자.
굳이 아래와 같이 B부터 비교할 필요가 없다.
이렇게 비교하면 된다.
이 때 위의 value 배열이 사용된다.
즉 첫번째 i=0, index = 0 부터 시작한 비교에서,
0~5까지는 글자가 모두 같았다.
그런데 6부터 글자가 다른 것이므로,
value[5] = 2를 index로 하여, 이 부분부터 다시 비교하면 된다.
즉, index : 6 => 2
가 된 상황이다.
i = 6 그대로이다.
정리하자면, i = 6부터 글자가 다르므로
1) i = 6 : 문자열 all의 6번째 글자(C) 와
2) index = 2 : 문자열 part의 2번째 글자(C) 를 비교하는 것을 볼 수 있다.
그러면 왜 이렇게 비교하는지 생각해보자.
value 배열은 문자열 part의 0~i번째까지 부분 문자열 중 접두사와 접미사가 같은 최대 길이이다.
첫번째 비교에서
ABCDAB 문자열이 같다. 즉 index = 5 까지 글자가 같다.
그리고 value[5] = 2로, 즉 이 문자열에는 앞 뒤로 AB가 있다.
part 문자열의 앞 부분인 AB가 all 문자열에 4,5번째에 있다는 것을 알 수 있기 때문에
이런식으로
그 다음 문자부터 비교하면 되는 것이다.
코드를 보면 다음과 같다.
public static void kmp() {
int index = 0;
for(int i=0; i<n; i++) {
// 1)
while(index >0 && all.charAt(i) != part.charAt(index)) {
index = value[index-1];
}
// 2)
if(all.charAt(i) == part.charAt(index)) {
// 2-1)
if(index == m-1) {
index = value[index];
// 2-2)
}else {
index++;
}
}
}
}
all 문자열 => ABCDABCDABEF
part 부분 문자열 => ABCDABE
n : all 문자열 길이
m : part 문자열 길이
index : part 문자열의 인덱스
코드를 설명하자면 다음과 같다.
일단 i = 0, index = 0 부터 시작한다.
i는 계속 증가시키고,
index는 변화가 생기는데,
코드 2-2)
만약 all 문자열의 i번째 문자와
part 문자열의 index 번째 문자가 같으면
index를 증가시킨다.
즉, i도 증가시키고, index도 증가시키면서 계속 두 문자열을 비교하면 된다.
코드 2-1)
index = m-1
즉, index 가 0부터 시작해서
part 문자열의 길이와 동일해지면,
all 문자열과 part 문자열이 모두 일치하는 구간이 나온 것이다.
그러면 이제는 다른 문자를 비교하도록 이동해야 된다.
즉 이렇게 모든 글자가 일치한 뒤에는 이제 all 문자열의 11번째 F와 part 문자열을 비교해야 된다.
이때는 index = value[index]
이다.
즉, index = value[6] = 0 이다.
all 문자열의 ABCDABE에서는 더이상 접두사와 접미사가 똑같은 문자가 없기 때문에
다시 index = 0
이 된다.
즉, 문자열 F와 part 문자열의 0번째 문자열을 비교하는 것이다.
코드 1)
index >0
이라는 것은 문자열 all과 문자열 part 가 일치하는 부분이 있었다는 뜻이다.
그런데 i번째 all 문자열과 index 번째 part 문자열이 다른 상태이다.
그러면
index = value[index-1]
이다.
즉 아래의 상태처럼
ABCDAB까지 같은데, i = 6일때 서로 문자열이 다른 것이다.
그러면 index = value[5] = 2 가 되어서
이처럼
part 문자열의 2번째와 all 문자열의 6번째를 다시 비교한다.
4) value 배열 만들기
value 배열 만드는 방법을 설명해보겠다.
위에서와 다른 예제로 설명하겠다.
value 배열은 문자열 part에 대해 만드는 것으로,
문자열 part = ABABABCD
에 대해 만들어보자.
i = 5 번째를 보면,
0~i 까지 부분 문자열은 ABABAB 인데
접두사이면서 접미사인 문자열은 ABAB이다.
왠지 AB 일 것 같은데,
ABAB라니 헷갈린다.
value 배열이 어떻게 만들어지는지 살펴본다면 알 수 있을 것이다.
kmp 알고리즘과 비슷하게 만들어진다.
part 문자열과 part 문자열을 비교한다.
아래 표에서 첫번째 part 문자열의 인덱스는 i로
두번째 part 문자열의 인덱스는 index로 표시한다.
1.
i = 0 일때는
부분 문자열이 A밖에 없는 것이므로 접두사이면서 접미사인 문자열이 없다.
그래서 value[0] = 0
2.
i = 1 일때는 아래와 같다.
i= 1, index = 0 으로
위의 part 문자열 1번째와
아래 part 문자열 0번째와 비교한다.
이때는 0~1 까지의 부분 문자열이 AB로,
표에서 보면 파란색 부분, 즉 A와 B가 다르다.
때문에 접두사이면서 접미사인 문자열이 없고
value[1] = 0 이다.
만약 AB가 아니라
AA였다면,
AA
AA 로 비교했을 때
A가 같아서 value[1] = 1 이었을 것이다.
즉, 표에서 위에 있는 part 문자열은 그대로 두고
아래에 있는 part 문자열의 위치를 이동시키면서 같은 문자열이 있는지 비교한다.
위에 있는 part 문자열 => 부분 문자열의 접미사 부분
아래에 있는 part 문자열 => 부분 문자열의 접두사 부분
이 두 부분이 같은지 비교하는 거라고 생각하면 된다.
3.
i = 2 일때는 부분 문자열이 ABA 이다.
즉 접두사이면서 접미사인 문자열이 A이다.
위의 part 문자열 2번째와 아래 part 문자열 0번째를 비교한다.
A로 같기 때문에
value[2] = 1 이 된다.
이렇게 같은 문자열이 나오면, 두번째 part 문자열을 오른쪽으로 이동시키지 않고 다음 문자열이 같은지 비교한다.
4.
i = 3 일때는 부분 문자열이 ABAB이다.
접두사이면서 접미사인 문자열이 AB로,
아래와 같이 AB가 같아서
value[3] = 2 이다.
이때는 위의 part 문자열 3번째와
아래 part 문자열 1번째를 비교한 것이다.
5.
i = 4
부분 문자열 : ABABA
접두사이면서 접미사인 문자열 : ABA
value[4] = 3
6.
i = 5
부분 문자열 : ABABAB
접두사이면서 접미사인 문자열 : ABAB
value[5] = 4
7.
i = 6
부분 문자열 : ABABABC
이제 문자열 C와 A가 다르기 때문에,
두번째 part 문자열을 오른쪽으로 이동시켜야 한다.
kmp 알고리즘에서도
문자열을 비교하다가 문자열이 다르면
value 배열을 이용해서 위치를 이동시켰던 것처럼
여기서도 value 배열을 이용해서 part 문자열이 오른쪽으로 몇 번 이동할지 결정한다.
index = 4 일때부터 문자열이 달랐다.
즉, index = 3 일때까지는 문자열이 같았기 때문에,
index = value[3] = 2 가 된다.
그래서, 위의 part 문자열 6번째와
아래 part 문자열의 2번째를 비교한다.
즉, value 배열을 통해서
위의 part 문자열의 4번째, 5번째 문자와
아래의 part 문자열의 0번째, 1번째 문자가 같다는 것을 알기 때문에
위의 part 문자열 6번쨰와 아래의 part 문자열 2번째를 비교하는 것이다.
하지만 여전히 문자가 다르다.
그러면 또 index = 1까지는 문자열이 같기 때문에
index = value[0] = 0 이 된다.
그래서 위의 part 문자열 6번째와
아래 part 문자열의 0번째를 비교한다.
이런식으로 비교해나가면 된다.
코드로 살펴보자면 다음과 같다.
public static void makeValue() {
int index = 0;
for(int i = 1; i<m ; i++) {
// 1)
while(index >0 && part.charAt(i)!= part.charAt(index)) {
index = value[index-1];
}
// 2)
if(part.charAt(i)== part.charAt(index)) {
index++;
value[i] = index;
}
}
}
코드 2)
아래처럼 위의 part 문자열과 아래의 part 문자열이 같은 상태일 때
아래의 part 문자열을 오른쪽으로 이동시키지 않고 index를 증가시켜서 다음 문자들을 비교한다고 했다.
즉 이 경우는 i= 2, index = 0 이므로
위의 part 문자열 2번쨰와 아래 part 문자열 0번째를 비교한다.
그런데 이 때 index = 1 로 증가시킨 뒤
value[2] = 1 이 된다.
그리고
아래의 경우는 위에서 index가 1 증가해서
위의 part 문자열 3번째와 아래의 part 문자열 1번째와 비교하게 된다.
그런데 문자열이 또 일치하기 때문에
index = 2 가 되고
value[3] = 2 가 된다.
코드 1)
아래의 경우처럼 index = 4인 상태에
위의 part 문자열 6번째와 아래 part 문자열 4번째가 다르면
index = value[index-1] = value[3] = 2
가 된다고 위에서 설명했다.
2. 최종 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
static int value[];
static int n;
static int m;
static String all;
static String part;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
all = br.readLine();
part = br.readLine();
n = all.length();
m = part.length();
value = new int[m];
makeValue();
kmp();
}
public static void makeValue() {
int index = 0;
for(int i = 1; i<m ; i++) {
while(index >0 && part.charAt(i)!= part.charAt(index)) {
index = value[index-1];
}
if(part.charAt(i)== part.charAt(index)) {
index++;
value[i] = index;
}
}
}
public static void kmp() {
int sum = 0;
StringBuilder result = new StringBuilder();
int index = 0;
for(int i=0; i<n; i++) {
while(index >0 && all.charAt(i) != part.charAt(index)) {
index = value[index-1];
}
if(all.charAt(i) == part.charAt(index)) {
if(index == m-1) {
sum++;
result.append(i-index+1).append(" ");
index = value[index];
}else {
index++;
}
}
}
System.out.println(sum);
System.out.println(result.toString());
}
}
참고 블로그 :
https://loosie.tistory.com/192
[알고리즘] 문자열 매칭 알고리즘 KMP (Java)
문자열 매칭 알고리즘 특정한 글이 있을 때 그 글 안에서 하나의 문자열을 찾는 알고리즘이다. 워드파일 또는 웹 브라우저 DB에서 문자열을 검색할 때 패턴 매칭 알고리즘을 사용하여 검색 결과
loosie.tistory.com
https://girawhale.tistory.com/44
[문자열 검색] KMP 알고리즘
단순하게 문자열을 찾는 방법을 생각해 보면 한 칸씩 비교해가며 일치하는지 확인하는 방법이 있다. ABABABC에서 ABAB가 몇 번 들어가는지 확인하는 예시이다. ⇒ 일치 ⇒ 불일치 ⇒ 일치 ⇒ 불일치
girawhale.tistory.com
https://bowbowbow.tistory.com/6
KMP : 문자열 검색 알고리즘
문자열 검색이 뭐지? 워드프로세서를 사용할 때 찾기 기능을 사용한적 있을 겁니다. 브라우저에서도 Ctrl+F 단축키를 눌러 검색할 수 있습니다. 아래 이미지는 브라우저에서 "테이프"를 검색했
bowbowbow.tistory.com