이 포스팅은 <프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략>, 구종만, 인사이트(2012)을 읽고 개인 학습용으로 정리한 글입니다.
S의 부분 문자열(substring)
= 문자열 S의 i번 글자부터 j번 글자까지로 구성된 문자열
= S[i..j]
S의 접두사(prefix)
= 문자열 S의 0번 글자부터 a번 글자까지로 구성된 문자열
= S[...a]
S의 접미사(suffix)
= 문자열 S의 b번 글자부터 끝까지로 구성된 문자열
= S[b...]
//H의 부분 문자열로 N이 출현하는 시작 위치들을 모두 반환
vector<int> naiveSearch(const string& H, const string& N){
vector<int> ret;
//모든 시작 위치를 다 시도
for(int begin = 0; begin < H.size(); ++begin){
bool matched = true;
for(int i = 0; i<N.size(); ++i){
if(H[begin+i] != N[i]){
matched = false;
break;
}
}
if(matched) ret.push_back(begin);
}
return ret;
}
커누스-모리스-프랫(Knuth-Moris-Pratt) 알고리즘
= KMP 알고리즘
현재 시작 위치에서 H와 N을 비교했을 때 몇 글자나 일치했는가를 이용하여
현재 H내에서의 뮈치나 H에 포함된 문자들을 보지 않고도
시작 위치 중 일부는 답이 될 수 없음을 보지 않고도 알 수 있다
시작 위치 i + k에서 답을 찾을 수 있기 위해서는N[ ... matched-1 ]의 길이 matched - k인 접두사와 접미사가 같아야 한다
답이 될 수 있는 바로 다음 위치를 찾기 위해서는 N의 각 접두사에 대해 접두사도 되고 접미사도 되는 문자열의 최대 길이를 계산해 두면 된다
-> 전처리 과정에서 부분 일치 테이블(partial match table) pi[] 계산
-> pi[i]: N[...i]의 접두사도 되고 접미사도 되는 문자열의 최대 길이
시작 위치 i에서 H와 N을 비교했을 때 matched 글자가 일치하고, 다음 글자가 불일치한 상황
-> 시작 위치 matched - pi[matched-1] 만큼 증가
시작 위치를 움직인 이후 첫 글자부터 다시 대응시켜 나갈 필요 X
-> N의 첫 pi[matched-1] 글자는 대응되는 H의 글자와 일치한다는 사실을 이미 알고 있다
-> matched를 pi[matched-1]로 변경하고 비교를 계속한다
matched = 0인 경우는 예외 처리
-> 모든 글자가 불일치한 경우 바로 다음 시작 위치에서 처음부터 다시 검색을 재개하는 방법 밖에 없다
//KMP 알고리즘을 이용하여 H의 부분 문자열로 N이 출현하는 시작 위치들을 모두 반환
vector<int> kmpSearch(const string& H, const string& N){
int n = H.size();
int m = N.size();
vector<int> ret;
//pi[i]: N[...i]의 접두사도 되고 접미사도 되는 문자열의 최대 길이
vector<int> pi = getPartialMatch(N);
//begin = matched = 0 부터 시작
int begin = 0, matched = 0;
while(begin <= n-m){
//H의 해당 글자가 N의 해당 글자와 같은 경우
if(matched < m && H[begin + matched] == N[matched]){
++matched;
//N의 모든 글자가 일치한 경우 답에 추가
if(matched == m) ret.push_back(begin);
}
else{
//matched = 0인 경우 다음 시작 위치에서 처음부터 다시 검색을 재개
if(matched == 0) ++begin;
else{
begin += matched - pi[matched-1];
matched = pi[matched-1];
}
}
}
return ret;
}
getPartialMatch() 함수 구현하기
가장 간단한 방법: N의 각 접두사에 대해 가능한 답을 하나씩 모두 시도
-> 길이 p인 접두사 N[ ... p-1]이 주어졌을 때 길이 p-1인 접두사, 길이 p-2인 접두사, 길이 p-3인 접두사, ... 를 순회하며 N[ ... p-1]의 접미사가 되는지 확인
-> 시간 복잡도 O( |N|^3 )
최적화할 수 있는 방법: 각 접두사에 대해 pi[]값을 따로 계산하는 것이 아니라 모든 접두사에 대해 한꺼번에 계산
-> 두 글자 N[i]와 N[begin+i]가 일치할 때마다 pi[begin + i] 갱신
-> 시간 복잡도 O( |N|^2 )
pi[begin + i] = max(pi[begin + i], i + 1)
-> 현재보다 왼쪽에 있는 시작 위치에서 이 위치의 값을 갱신했을지도 모르기 때문에 이미 있는 값과 i+1 중 큰 값을 선택한다
//N에서 자기 자신을 찾으면서 나타나는 부분 일치를 이용해 pi[]계산
//pi[i]: N[...i]의 접두사도 되고 접미사도 되는 문자열의 최대 길이
vector<int> getPartialMatchNaive(const string& N){
int m = N.size();
vector<int> pi(m,0);
//단순 문자열 검색 알고리즘 구현
for(int begin = 1; begin < m; ++begin){
for(int i = 0; i + begin < m; ++begin){
if(N[i] != N[begin+i]) breaK;
//i+1 글자가 서로 대응됨
pi[begin + i] = max(pi[begin + i], i + 1);
}
}
return pi;
}
vector<int> getPartialMatch(const string& N){
int m = N.size();
vector<int> pi (m,0);
//KMP 알고리즘을 이용하여 문자열 검색
//N에서 N을 찾는다
//begin = 0이면 자기 자신을 찾아버리므로 begin = 1부터 시작
int begin = 1;
int matched = 0;
//비교할 문자가 N의 끝에 도달할 때 까지 찾으면서 부분 일치를 모두 기록
while(begin + matched < m){
if(N[matched] == N[begin + matched]){
++matched;
//pi[]의 각 원소는 한 번만 변경되기 때문에 max()연산 필요X
pi[begin + matched - 1] = matched;
}
else{
if(matched == 0) ++begin;
else{
//begin을 옮길 때 이전에 계산한 pi[]값 사용
begin += matched - pi[matched - 1];
matched = pi[matched - 1];
}
}
}
return pi;
}
긴 문자열 S가 주어질 때 이 문자열의 접미사도 되고 접두사도 되는 문자열들의 길이를 전부 출력하는 문제
ex. S = "ababbaba" 라고 하면 "a", "aba"는 이 문자열의 접미사도 되고 접두사도 된다
-> 답: 1, 3, 8(=|S|)
간단한 방법: S의 모든 접두사에 대해 문자열 S의 접미사이기도 한지 확인
-> |S|개의 접두사가 있고 각 접두사를 확인하는 데 접두사의 길이에 비례하는 시간이 걸린다
-> 시간 복잡도 O(|S|^2)
KMP 알고리즘에서 사용하는 부분 일치 테이블 pi[]를 만들면 접두사도 되고 접미사도 되는 문자열의 최대 길이를 구할 수 있다
-> S = "ababbaba" 일 때 pi[7] = 3
-> 이보다 짧은 답은 어떻게 구할 수 있을까?
S의 길이 k인 접두사와 접미사는 서로 같다
따라서 길이가 k이하인 S의 접미사는 S[...k-1]의 접미사이기도 하다
-> ex. S = "ababbaba"에서 "aba"보다 짧은 답 "a"는 S의 접미사이기도 하지만, S[...2] = "aba"의 접미사 이기도 하다
-> 따라서 k 다음으로 짧은 접미사를 찾으려면 p[k-1]을 확인하면 된다
//s의 접두사도 되고 접미사도 되는 모든 문자열의 길이를 반환
vector<int> getPrefixSuffix(const string& s){
vector<int> ret;
vector<int> pi = getPartialMatch(s);
int k = s.size();
while(k > 0){
ret.push_back(k);
k = pi[k-1];
}
return ret;
}
팰린드롬(palindrome): 앞에서 읽었을 때와 뒤로부터 읽었을 때 똑같은 문자열
주어진 문자열 S 뒤에 적절한 문자열을 붙여서 S를 팰린드롬으로 만들려고 한다
문자열 S를 뒤집은 문자열을 S뒤에 붙이면 항상 팰린드롬이 되지만, 결과 팰린드롬이 가능한 한 짧았으면 한다
ex. S = "anon"일 때
-> "nona"를 붙여서 "anonnona"로 만들 수 있다
-> "ona"를 붙여서 "anonona"로 만들 수 있다
-> "a"를 붙여서 "anona"로 만들 수 있다
문제를 푸는 방법: 우선 S를 뒤집은 문자열 S′을 만든 뒤, S의 접미사이면서 S′의 접두사인 문자열을 찾는다
-> 이 문자열을 제외한 S′의 남은 부분을 S의 뒤에 붙이면 팰린드롬을 만들 수 있다
//KMP 알고리즘 변형
//a의 접미사이면서 b의 접두사인 문자열의 최대 길이를 구한다
int maxOverlap(const string& a, const string& b){
int n = a.size();
int m = b.size();
vector<int> pi = getPartialMatch(b);
//begin = matched = 0 에서 시작
int begin = 0;
int matched = 0;
while(begin < n){
if(matched < m && a[begin + matched] == b[matched]){
++matched;
//a의 마지막 글자와 b의 문자가 서로 일치했을 때
//지금까지 일치한 부분의 길이 반환
if(begin + matched == m)
return matched;
}
else{
if(matched == 0) ++begin;
else{
begin += matched - pi[matched - 1];
matched = pi[matched-1];
}
}
}
return 0;
}
- 전체 문자열은 접두사와 접미사가 같기 때문에 가장 먼저 문자열의 길이를 정답으로 넣어준다
- 그 다음의 위치 k를 pi[k-1]로 가르키면서 k가 0이 될 때까지 반복해주면 답을 구할 수 있다
vector<int> kmpSearch2(const string& H, const string& N){
int n = H.size();
int m = N.size();
vector<int> ret;
vector<int> pi = getPArtialMatch(N);
//현재 대응된 글자 수
int matched = 0;
//문자열 H의 각 글자 순회
for(int i = 0; i <n; ++i){
//matched번 글자와 H의 해당 글자가 불일치할 경우
//현재 대응된 글자 수를 pi[matched-1]로 줄인다
while(matched > 0 && H[i] != N[matched])
matched = pi[matched-1];
//글자가 대응될 경우
if(H[i] == N[matched]){
++matched;
if(matched == m) ret.push_back(i);
matched = pi[matched-1];
}
}
}
문자열 H가 문자열 N을 포함한다면 항상 N은 H의 어떤 접미사의 접두사
-> H의 접미사 배열을 이진 탐색해서 각 문자열이 출현하는 위치를 찾을 수 있다
접미사 배열의 길이 는 항상 |H|이므로 이진 탐색 내부 수행 횟수: O( lg|H| )번
이진 탐색 내부에서 문자열 비교 시간: O( |N| )
-> 이진 탐색 수행 시간 O( |N| lg|H| )
//두 접미사의 시작 위치 i,j가 주어질 때 두 접미사 중 어느 쪽이 앞에 와야 할지 비교
struct SuffixComparator{
const string& s;
//구조체 생성자
SuffixComparator(const string& s): s(s) {}
bool operator () (int i, int j){
//s.substr()대신에 strcmp()를 사용하여 임시 객체를 만드는 비용 절약
//c_str(): c++ string을 c style char*로 변환
//s.c_str() + i < s.c_str() + j 이면 true
return strcmp(s.c_str() + i, s.c_str() + j) < 0;
}
};
//s의 접미사 배열을 계산한다
vector<int> getSuffixArrayNaive(const string& s){
//접미사의 시작 위치를 담은 배열
vector<int> perm;
for(int i = 0; i < s.size(); ++i)
perm.push_back(i);
//접미사를 비교하는 비교자를 이용하여 정렬
sort(perm.begin(), perm.end(), SuffixComparator(s));
return perm;
}
정렬을 여러 번 하는 데도 더 빠르게 동작하는 이유:
이전 정렬에서 얻은 정보를 이용해 두 문자열의 대소 비교를 O(1)에 할 수 있다
group[i] = S[i..]가 속한 그룹의 번호
첫 t 글자를 기준으로 만든 group[]이 있을 때
S[i..], S[j..] 중 첫 t 글자를 기준으로 어느 쪽이 더 앞에 오는 지 확인하는 방법:
group[i]와 group[j]를 비교하면 알 수 있다
S[i..], S[j..] 중 첫 2t 글자를 기준으로 어느 쪽이 더 앞에 오는 지 확인하는 방법:
우선, 첫 t 글자를 기준으로 어느 쪽이 더 앞에 오는지 확인
-> group[i]와 group[j] 비교
만약 두 접미사가 같은 그룹에 속한다면, S[i+t..]와 S[j+t ..]의 첫 t 글자를 기준으로 어느 쪽이 더 앞에 오는지 확인
-> group[i+t]와 group[j+t] 비교
첫 t 글자로 묶인 그룹 정보를 이용해 첫 2t 글자를 비교하는 비교자의 구현
//각 접미사들의 첫 t 글자를 기준으로 한 그룹 번호가 주어질 때
//주어진 두 접미사를 첫 2t 글자를 기준으로 비교한다
//group[]은 길이가 0인 접미사도 포함한다
struct Comparator{
const vector<int>& group;
int t;
Comparator(const vector<int>& _group, int _t): group(_group),t(_t){
group = _group;
t = _t;
}
bool operator() (int a, int b){
//첫 t 글자가 다른 그룹에 속하는 경우
if(group[a] != group[b]) return group[a] < group[b];
//첫 t 글자가 같은 그룹에 속하는 경우
return group[a+t] < group[b+t];
}
};
group[a+t]와 group[b+t]가 배열 밖의 범위인지 확인할 필요 X
-> group[a+t]와 group[b+t]를 참조하는 경우 = group[a]와 group[b]가 같은 경우 = 두 접미사의 첫 t 글자가 같은 경우
-> S[a..]와 S[b..]는 서로 다른 두 접미사이기 때문에 두 접미사의 길이는 모두 t 이상이 된다
(a+t 와 b+t는 최대 n)
⚡접미사 배열을 계산하는 맨버와 마이어스 알고리즘
//s의 접미사 배열을 계산한다
vector<int> getSuffixArray(const string& s){
int n = s.size();
//group[i] = 접미사들을 첫 t 글자를 기준으로 정렬했을 때,
//S[i..]이 들어가는 그룹의 번호
//t = 1일 때는 S[i..]의 첫 글자로 그룹 번호를 정해줘도 같은 효과가 있다
int t = 1;
vector<int> group(n+1);
//S[n..]: 길이가 0인 접두사는 -1 번 그룹에 고정
group[n] = -1;
for(int i = 0; i<n; ++i)
group[i] = s[i];
//결과적으로 접미사 배열이 될 반환값
//접미사의 시작 위치 저장
vector<int> perm(n);
//모든 접미사의 시작 위치 저장
for(int i = 0; i<n; ++i)
perm[i] = i;
while(t < n){
//첫 t 글자를 기준으로 계산된 group[]을 이용하여
//첫 2t 글자를 기준으로 perm[]을 다시 정렬한다
Comparator compareUsing2T(group, t);
sort(perm.begin(), perm.end(), compareUsing2T);
t *= 2;
if(t >= n) break;
//첫 2t 글자를 기준으로 group[] 새로 계산
vector<int> newGroup(n+1);
//S[n..]: 길이가 0인 접두사는 -1 번 그룹에 고정
newGroup[n] = -1;
for(int i = 1; i<n; ++i){
if(compareUsing2T(perm[i-1], perm[i])){
newGroup[perm[i]] = newGroup[perm[i - 1]] + 1;
}
else{
newGroup[perm[i]] = newGroup[perm[i - 1]];
}
}
//group[] 갱신
group = newGroup;
}
return perm;
}
길이 n(n<=40000)인 문자열을 끝과 끝이 연결된 원형으로 써보자
이 문자열을 항상 시계 방향으로 읽는 데, 시작 위치가 어디인지는 정해져 있지 않으므로 n가지 방법으로 읽을 수 있다
이 중 사전순으로 가장 앞에 오는 문자열은?
주어진 문자열 S를 두 번 반복한 문자열 S2 를 만든다
이때 S를 읽을 수 있는 방법은 모두 S2의 부분 문자열이 된다
-> S2의 접미사 배열을 만든 뒤, 가장 앞에 오는 길이가 n 이상인 접미사를 찾으면 된다
//사전순으로 가장 앞에 오는 s의 회전 결과를 구한다
string minShift(const string& s){
string s2 = s + s;
vector<int> a = getSuffixArray(s2);
for(int i = 0; i<a.size(); ++i)
//접미사가 시작하는 위치 a[i]가 s.size()보다 커지면
//접미사의 길이가 s.size()보다 짧아진다
if(a[i] <= s.size())
return s2.subarray(a[i], s.size());
//여기까지 올 일은 없어야 한다
return "__oops__"
}
- C++의 string을 C style의 char*로 변환
-> c_str() ~ c_str() + size() 까지 C++의 string이 저장되어 있고, 맨 마지막 위치에 NULL 문자가 오게 된디- c_str() 이 리턴하는 배열을 수정하는 것은 정의되지 않는 작업 (undefined behavior)이다
- 매개변수로 들어온 두 개의 문자열을 비교하여 문자열이 완전히 같다면 0을 반환하고,
다르면 음수 혹은 양수를 반환하는 함수
-> str1 < str2 인 경우에는 음수 반환
-> str1 > str2 인 경우에는 양수 반환
-> str1 == str2 인 경우에는 0을 반환- 앞에서 부터 각각 문자를 비교할때, 아스키 코드값으로 비교를 하게 됩니다.
길이 n(n<= 4000)인 문자열은 최대 n(n+1)/2 개의 부분 문자열을 가질 수 있지만, 이들이 모두 서로 다른 것은 아니다
문자열이 주어질 때 이들의 서로 다른 부분 문자열의 수를 세는 문제
가장 간단한 방법:
각 부분 문자열을 직접 만들어 보면서 이들을 집합 자료 구조에 넣는 것
-> O(n^2)개의 부분 문자열
C++ set< > 자료구조 넣기 위한 비교 횟수: O(lgn)번
문자열 비교 시간: O(n)
-> 전체 시간 복잡도 O(n^3 lgn)
한 부분 문자열이 두 번 이상 출연할 경우 이를 접두사로 갖는 접미사들을 접미사 배열 상에서 항상 인접하다
-> 따라서 한 부분 문자열이 이미 출현했는지를 알기 위해서는 바로 위 접미사만을 보면 된다
각 접미사에 대해 배열에서 자기 앞에 오는 배열과 최장 공통 접두사의 길이를 구하면, 이만큼은 중복되는 부분 문자열임을 이용할 수 있다
//s[i..]와 s[j..]의 공통 접두사의 최대 길이 계산
int commonPrefix(const string& s, int i, int j){
int k = 0;
while(i < s.size() && j < s.size() && s[i] == s[j]){
++i; ++j; ++k;
}
return k;
}
//s의 서로 다른 부분 문자열의 수를 센다
int countSubstrings(const string& s){
//문자열 s의 모든 접미사를 사전순으로 정렬해둔 벡터
//접미사가 시작하는 위치 저장
vector<int> a = getSuffixArray(s);
int ret = 0;
for(int i = 0; i < a.size(); ++i){
int cp = 0;
if(i > 0) cp = commonPrefix(s, a[i-1],a[i]);
//a[i]의 (a.size() - a[i])개의 접두사들 중 cp개는 중복이다
ret += s.size() - a[i] - cp;
}
return ret;
}