"두 문자열 S, target이 주어질 때 문자열 S에서 문자열 target을 찾고 그 시작 위치를 구하라."
이 문제를 다음과 같은 순서로 해결하고자 한다.
- 단순한 구현
- KMP 알고리즘
- KMP 알고리즘과 부분 일치 테이블의 구현
- 백준 1786
1. 단순한 구현
1) 알고리즘 및 구현
문자열 검색하면 가장 처음에 떠올릴 법한 구현으로, 문자열 S의 시작점을 변경해가며 비교하는 방법이 있다. S = "abcabc", target = "ab" 라고 가정해 보자. 다음 과정을 통해 시작점을 구할 수 있다.
begin = 0
| 문자열 S | a | b | c | a | b | c |
| 문자열 target | a | b | ||||
| 비교 결과 | O | O |
begin = 1
| 문자열 S | a | b | c | a | b | c |
| 문자열 target | a | b | ||||
| 비교 결과 | X | 비교하지 않음 |
begin = 2
| 문자열 S | a | b | c | a | b | c |
| 문자열 target | a | b | ||||
| 비교 결과 | X | 비교하지 않음 |
begin = 3
| 문자열 S | a | b | c | a | b | c |
| 문자열 target | a | b | ||||
| 비교 결과 | O | O |
begin = 4
| 문자열 S | a | b | c | a | b | c |
| 문자열 target | a | b | ||||
| 비교 결과 | X | 비교하지 않음 |
begin = 5부터는 실행할 필요 없음.
아래는 이것을 코드로 옮긴 것이다.
bool equals(string S, string target, int begin) {
for (int i = 0; i < target.size(); ++i) {
if (S[begin + i] != target[i]) return false;
}
return true;
}
int main() {
string S, target;
getline(cin, S);
getline(cin, target);
vector<int> result;
// 남은 문자열 S의 길이가 target의 길이이상이어야 함.
int last = S.size() - target.size();
for (int begin = 0; begin <= last; ++begin) {
if(equals(S, target, begin)) result.push_back(begin);
}
// 결과 출력
for (int index : result) {
cout << index << endl;
}
return 0;
}
2) 단순한 구현 시간복잡도
이 방법을 사용해도 대부분의 경우 나쁘지 않은 성능을 보여줄 것이다. S와 target을 비교하다가 중간에 일치하지 않는 부분이 있다면 끝까지 확인하지 않고 넘어가기 때문이다. 따라서 평균적인 성능은 O(N)이 될 것이다.(N = S의 길이) 하지만 S="aaaaaaaaaa", target="aaaaaab"와 같은 최악의 경우를 만난다면 항상 target 전체를 비교해야 한다. 따라서 최악의 경우 시간복잡도는 O(NM)이 된다.(M = target의 길이)
| a | a | a | a | a | a | a | a | a | a |
| a | a | a | a | a | a | b | |||
| (비교) | O | O | O | O | O | O | X |
2. KMP 알고리즘
1) 핵심 아이디어
최악의 경우를 다시 생각해 보자. S="aaaaaaaaaa", target="aaaaaab" 에서 begin = i 를 확인했더니 앞에서부터 6개의 문자가 일치한다. 그리고 begin + 1로 옮겨서 다시 비교해 보자.
| a | a | a | a | a | a | a | a | a | a |
| a | a | a | a | a | a | b | |||
| (비교) | O | O | O | O | O | ? | ? |
target이 aaaaaab이기 때문에 6번째까지 일치했다면 1칸 옮겨서 비교하더라도 5번째까지는 일치할 것이다. 따라서 다음 번 비교에는 굳이 5번째까지는 비교할 필요가 없다. 이를 조금더 일반화 시켜서 S="aabaabaabc", target="aabaabc" 를 생각해보자.
begin = 0
| a | a | b | a | a | b | a | a | b | c |
| a | a | b | a | a | b | c | |||
| O | O | O | O | O | O | X |
6번째(taget[5])까지 일치했다. 다음 비교를 위해 몇 칸을 움직이는 게 적절할까? 당연히 3칸 움직이는 게 가장 효율적일 것이다. 그래야 문자열이 일치할 가능성이 있다. 1~2칸 옮겼을 경우는 가능성이 없다는 것을 알기 때문에 비교하지 않아도 된다. 아래는 3칸 옮긴 직후다.
begin = 3
| a | a | b | a | a | b | a | a | b | c |
| a | a | b | a | a | b | c | |||
| O | O | O | ? | ? | ? | ? |
이전에 6번째(S = "aabaab...")까지 일치했다. 그 상태에서 3칸 이동했기 때문에 적어도 앞의 세 자리는 "aab"라는 것을 알 수 있다. 이 부분은 다시 비교할 필요가 없다. 즉, S와 target 문자열을 비교했을 때 일치한 길이를 알면 다음 비교 위치를 몇 칸 이동하고, 몇 번째까지는 비교하지 않아도 된다는 정보를 미리 알 수 있다. 이 정보는 target을 통해 미리 배열로 만들어둘 수 있다. 이 배열을 부분 일치 테이블이라고 부르고, 이 테이블을 만드는 과정을 전처리라고 한다. (부분 일치 테이블은 실패했을 때 어떻게 해야할 지 말해준다는 의미에서 실패함수라고도 부른다.)
2) 부분 일치 테이블
(matched는 부분 일치한 문자열의 길이이다.) S와 target이 target[matched - 1]까지 일치했다면 다음 비교위치로 몇 칸 이동해야 하는지 어떤 기준으로 구할 수 있을까? 먼저 target[matched - 1]까지의 부분 문자열을 생각해 보자. target = "aabaabc"에서 matched = 6라면 부분 문자열은 "aabaab"가 된다. 이 경우 3칸을 이동하면 되는데, 그 이유는 앞에서 세 글자("aab")가 뒤에서 세 글자("aab")와 같기 때문이다. 접두사와 접미사의 길이를 k라 할 때 접두사와 접미사가 같은 최대 k를 구하면 된다. 부분 일치 테이블을 구하면 다음과 같다. (k는 부분문자열의 길이보다 작다)
| matched - 1 | k |
| 0 | 0 |
| 1 | 1 |
| 2 | 0 |
| 3 | 1 |
| 4 | 2 |
| 5 | 3 |
| 6 | 0 |
예를 들어 matched = 5라면 부분문자열은 "aabaa" 이고, 가장 긴 접두사와 접미사는 "aa"이다. 따라서 k = 2이다. 이 배열을 pi라고 할 때 target[matched - 1]까지 일치하면 다음 시작 위치는 matched - pi[matched - 1] 만큼 이동하면 되고, 이동 후 target[matched]까지는 비교하지 않아도 된다.
계산 식에 대한 설명이다. 식이 바로 이해가 됐다면 넘어가도 된다. pi[matched - 1]는 공통 접두사와 접미사의 길이이다. 접미사의 시작 위치로 옮기더라도 이 길이만큼은 이미 일치함을 알고 있다. 따라서 다음 위치는 접미사의 시작점이 되어야 한다. 빨간 화살표만큼 이동해야 접미사의 시작점으로 이동하므로 위와 같은 식이 나온다. 부분 일치 문자열의 길이가 짧으면 다음 시작 위치를 많이 건너뛰게 된다. 부분 일치 문자열의 길이가 길다면 다음 시작 위치는 가깝지만 비교 연산을 덜 해도 된다.
3. KMP 알고리즘과 부분 일치 테이블의 구현
1) KMP 알고리즘의 구현
위 내용을 코드로 옮기면 다음과 같다. pi는 부분 일치 테이블이고, 부분 일치 테이블은 이미 초기화 되어 있다고 가정한다.
// 시작 위치를 모두 구해 반환한다. 시작 위치는 index가 아닌 index + 1 로 구한다. (백준 1786)
vector<int> getBegins(string S, string target, vector<int>& pi) {
int n = S.size();
int m = target.size();
vector<int> res;
int begin = 0, matched = 0;
// 마지막에 도달할 때까지 반복
while (begin + m <= n) {
// 현재 비교한 문자가 일치
if (matched < m && S[begin + matched] == target[matched]) {
++matched;
if (matched == m) res.push_back(begin + 1); // target 발견
}
// 현재 비교한 문자가 불일치
else {
if (matched == 0) {
++begin;
} else { // 부분 일치된 문자열이 있을 경우
begin += matched - pi[matched - 1];
matched = pi[matched - 1];
}
}
}
return res;
}이 알고리즘의 시간복잡도는 얼마일까? 반복문의 분기가 두 개로 나뉘어 있어 직관적으로 구하기 어렵다. 문자열 비교시 S의 begin + matched 인덱스를 확인하는데, 최악의 경우에도 두 번 반복하면 begin + matched 값은 반드시 증가함을 알 수 있다. 따라서 시간 복잡도는 O(N)이다. (N = S의 길이)
2) 부분 일치 테이블의 구현 - 단순한 방법
부분 일치 테이블은 target의 부분 문자열의 길이를 바꿔가며 구할 수 있다. target = "aabaabc"라면 길이가 5일 때 "aabaa"와 "aabaa"가 일치할 때까지 구해주면 된다.
| a | a | b | a | a | ||
| 시도 1 | a (O) | a (X) | b | a | a | |
| 시도 2 | a (X) | a | b | a | a | |
| 시도 3 | a (O) | a(O) | b | a |
세 번째 시도에서 비교한 문자열이 일치했으므로 pi[4](pi[matched - 1])는 2라는 것을 구할 수 있다. 네 번째 시도는 해봐야 2보다 작기 때문에 수행할 필요가 없다. target의 부분 문자열의 길이를 l이라 가정하면 l일 때 부분 일치 값을 구하기 위해 O(l^2)의 시도가필요하다. target의 길이가 M이라면 총 O(M^3) 시간이 된다. target의 길이가 충분히 짧다면 문제가 되지 않겠지만, 의도적으로 target의 길이를 길게 설정하면 전처리 과정에서 너무 많은 시간이 소요된다.
3) 부분 일치 테이블의 구현 - 조금 향상된 방법
target의 부분 문자열이 아닌 전체를 대상으로, 시작 위치를 바꿔가며 M-1번 비교하는 방법을 활용할 수 있다.
| a | a | b | a | a | b | c | |||
| 시도1 | a | a | b | a | a | b | c | ||
| 시도2 | a | a | b | a | a | b | c | ||
| 시도3 | a | a | b | a | a | b | c | ||
| ... |
위 예제의 세 번째 시도에서 일치한 최대 길이는 3이다. 일치가 발생할 때마다 pi 테이블을 적절한 위치를 찾아 업데이트 해준다면 세 번째 시도만으로 pi[5], pi[4], pi[3]을 구할 수 있다. 이 때의 시간복잡도는 각 시도마다 M번 미만의 비교, 총 M-1번 시도하므로 O(M^2)이다. 그런데 여기서... KMP 알고리즘을 적용할 수 있다는 생각이 든다.
4) 부분 일치 테이블의 구현 - 근데 이제, KMP를 곁들인
부분 일치 테이블을 구현할 때 이전까지 구했던 부분 일치 테이블을 이용할 수 있다. 아래는 이를 구현한 코드이고 KMP 알고리즘과 거의 유사하다.
// 부분 일치 테이블을 구하여 반환한다.
vector<int> getPi(string target) {
int n = target.size();
vector<int> pi(n, 0);
// KMP와는 다르게 begin = 1부터 시작한다.
int begin = 1, matched = 0;
while (begin + matched < n) {
if (target[begin + matched] == target[matched]) {
++matched;
// KMP에서는 완전 일치된 문자열을 발견하면 시작 위치에 추가하지만, 여기서는 문자가 일치할 때마다 pi 테이블을 갱신해준다.
pi[begin + matched - 1] = matched;
}
else {
if (matched == 0) {
++begin;
}
else {
begin += matched - pi[matched - 1];
matched = pi[matched - 1];
}
}
}
return pi;
}이 때 시간복잡도는 KMP 알고리즘과 동일하게, begin + matched 값이 작아지지 않으므로 O(M)이다. 전처리 과정을 포함한 최종적인 KMP 알고리즘의 시간복잡도는 O(N + M)이다. 하지만 일반적으로 N > M 이기 때문에 O(N)으로 계산해도 무방하다.
4. 백준 1786번: 찾기
https://www.acmicpc.net/problem/1786
1786번: 찾기
첫째 줄에, T 중간에 P가 몇 번 나타나는지를 나타내는 음이 아닌 정수를 출력한다. 둘째 줄에는 P가 나타나는 위치를 차례대로 공백으로 구분해 출력한다. 예컨대, T의 i～i+m-1번 문자와 P의 1～m
www.acmicpc.net
KMP알고리즘을 활용한 백준 1786 문제에 대한 코드이다.
#include <iostream>
#include <string>
#include <cstdio>
#include <vector>
using namespace std;
vector<int> getPi(string target) {
int n = target.size();
vector<int> pi(n, 0);
int begin = 1, matched = 0;
while (begin + matched < n) {
if (target[begin + matched] == target[matched]) {
++matched;
pi[begin + matched - 1] = matched;
}
else {
if (matched == 0) {
++begin;
}
else {
begin += matched - pi[matched - 1];
matched = pi[matched - 1];
}
}
}
return pi;
}
vector<int> getBegins(string S, string target, vector<int>& pi) {
int n = S.size();
int m = target.size();
vector<int> res;
int begin = 0, matched = 0;
while (begin + m <= n) {
if (matched < m && S[begin + matched] == target[matched]) {
++matched;
if (matched == m) res.push_back(begin + 1);
}
else {
if (matched == 0) {
++begin;
} else {
begin += matched - pi[matched - 1];
matched = pi[matched - 1];
}
}
}
return res;
}
int main() {
string S, target;
getline(cin, S);
getline(cin, target);
vector<int> pi = getPi(target);
vector<int> result = getBegins(S, target, pi);
cout << result.size() << endl;
for (int i = 0; i < result.size(); ++i) {
printf("%d\n", result[i]);
}
return 0;
}Reference
- 프로그래밍 대회에서 배우는 알고리즘 문제해결 전략
'알고리즘' 카테고리의 다른 글
| [cpp]백준 14266번 나는 가르친다 스위핑을 (0) | 2021.09.19 |
|---|---|
| 알고리즘 및 코딩테스트 언어 고민 중이다. (0) | 2021.09.19 |
| [cpp]백준 1107번 리모컨 (0) | 2021.09.12 |
| 백준 14734번 Aztec Diamond (cpp) (1) | 2021.07.28 |
| 백준 1562번 계단수 (0) | 2021.07.21 |
