이사 중...
===============================================
아
하다가 멘탈 깨져서 정리함.
서픽스 어레이의 n^2logn 풀이는 아주 간단하다. 소스 코드만 정리해보자면 ...
1 2 3 4 5 6 7 8 9 10 | vector<int> getSuffixArray(const string& s){ vector<int> suffix; //suffix배열을 초기화 for (int i = 0; i < s.size(); ++i) suffix.push_back(i); //문자열을 비교( 람다함수 사용 ) sort(suffix.begin(), suffix.end(), [&s](int a, int b){ return strcmp(s.c_str() + a, s.c_str() + b) < 0; }); return suffix; // 리턴 } | cs |
아아아아아주 쉽다. 오히려 람다함수가 더 어려운듯...
방식자체는 설명하자면 n개의 문자열을 죄다 때려박은 후
(메모리를 적게 사용하기 위해서 인덱스만 때려박음 : 4번째 줄)
그 해당 문자열을 정렬한다. 근데 정렬하는데 드는 비용이 nlogn이고 하나의 문자열을 비교하는 비용이 n이므로 n^2logn이다.
굉장히 못써먹을 시간복잡도라고 생각할 수 있지만 사실 문자열을 비교하는데 일반적인 경우, 항상 n이 걸리지는 않기 때문에 그럭저럭 쓸만하다.
... 인풋이 aaaaaaaaaaaaaaaaaaaa... 만 아니라면...
이것보다 좋은 알고리즘으로는 맨버-마이어스의 알고리즘이 있다.
이 알고리즘의 시간복잡도는 n * log n * log n n을 로그로 떨군건데
난 멍청해서 이걸 이해하는데 엄청 오래걸렸다.
내가 구글링을 잘 못하는 걸 수도 있는데 제대로 정리된 블로그가 없어... 그래서 정리함.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 | std::vector<int> getSuffixArray(const string& s) { int n = s.size(); //idx + t 까지 비교한다! int t = 1; //group[i]는 t까지 비교했을 때 i의 그룹 번호 vector<int> group(n + 1); //t==0일때를 대신한 거라고 봐도 무방... for (int i = 0; i < n; ++i) group[i] = s[i]; group[n] = -1; //서픽스를 담을 배열 vector<int> suffix(n); //서픽스를 초기화 for (int i = 0; i < n; ++i) suffix[i] = i; while (t < n) { //비교함수 아주 중요함 auto cmp = [&group, t](int a, int b){ if (group[a] != group[b]) return group[a] < group[b]; return group[a + t] < group[b + t]; }; //정렬 std::sort(suffix.begin(), suffix.end(), cmp); t *= 2; //t가 n보다 크거나 같으면 종료 if (t >= n) break; //그룹 재지정 vector<int> newGroup(n + 1); newGroup[n] = -1; newGroup[suffix[0]] = 0; for (int i = 1; i < n; ++i){ if (cmp(suffix[i - 1], suffix[i])){ newGroup[suffix[i]] = newGroup[suffix[i - 1]] + 1; }else newGroup[suffix[i]] = newGroup[suffix[i - 1]]; } group = newGroup; } return suffix; } | cs |
람다함수 [&group,t] <= group은 레퍼런스로 참조하고 t는 값을 복사해서 사용한다.
나름대로 정리하자면
s ? 구하려는 서픽스 배열의 target 스트링
group[i] ? i번째 접미사가 가지는 그룹 번호(index순)
suffix[i] ? t까지 봤을때 i번째 접미사(사전 순)
t상태일때 어디까지 정렬되냐면 글자수가 2t일때까지 정렬된다.(즉 1일때는 글자수가 2개까지 정렬)
근데 이 그룹이라는 놈이 엄청나게 많은 것을 함축 하고 있는데
group[a]는 사실 string의 [a...a+t)까지 비교한 결과의 상대 값이 저장되어 있다고 보면 된다.
이걸 이해하는데 이틀걸림.
22~ 26줄의 compare함수를 보자.
case : group[a] != group[b]
group[a]와 group[b]가 다를 때 group[a] < group[b]를 리턴한다.
현재 t상태일때 벌써부터 group값이 다르다는 것은 이미 비교가 끝나있다는 것이다.
그러니 a+t번째는 비교해볼 가치도 없음.
case : group[a]와 group[b]가 같다.
string의 [a...a+t) [b...b+t)의 비교결과가 같다는 것이다.
그럼이제 이걸 신경 쓸 필요가 없지.
[a+t...a+2t)와 [b+t...b+2t) 만 비교하면 된다.
근데 이걸 일일이 다 비교하면 시간복잡도가 어마어마하게 증가한다.
비교 할때마다 t만큼 추가 시간이 걸리니 말이다.
그리고 다행스럽게도 이 결과는 이미 저장되어 있다.
어디에?
group[a+t]와 group[b+t]에!
그렇기 때문에 group[a+t]와 group[b+t]를 비교한 값을 리턴해주면 된다.
이 비교함수로 정렬이 완료되었으면 이제 이 결과를 다시 그룹에 반영해줘야 하는데
이부분이 37~46줄이다.
그룹의 값은 상대값이기 때문에 suffix의 첫번째 값은 0으로 설정하도록 하자.
이제부터 suffix[n-1]까지 갱신해주는데 비교했는데
이 비교의 기준은 이전 group과 t이다.(아직 갱신되기 전)
(실수로 t를 값이아니라 레퍼런스로 참조해봤는데 재밌는 일이 일어났다 ㅎㅎ)
case : suffix[i-1]과 suffix[i]를 비교
비교값이 더크데! <- 당연히 더 커야지 비교한 결과가...
즉 이미 비교가 완료된 항목임.
그러니까 상대값도 1증가시켜줌.
case : 현재까지 문자열을 사전순으로 비교할 수 없다.
suffix배열은 t까지 진행했을때 정렬되어 있어야한다.
즉 이부분은 아직 정렬이 제대로 이뤄지지 않았다는 것이고
따라서 아직까지는 suffix[i]와 suffix[i-1]은 누가더 사전순으로 우선인지 알 수 없다.
즉 suffix[i]와 suffix[i-1]은 길이가 2t일때까지 같았다는 것
그룹번호를 같게 유지해서 다음 시퀀스에 비교할 수 있게 해두자.
(서픽스 어레이의 특성상 모든 문자열의 길이가 다르기때문에 같은건 존재할수없다.)
다른사람이 이해가 됐을지 모르겠다.
내가 나중에 봤을때 이해할 수 있을 정도로만 정리해둔거라...
틀린부분 있다면 지적부탁드려용.
참고 : 알고리즘 문제해결 전략 2권 suffix array파트 참조
p.s. suffix array관한 풀이는 최대 n까지 줄일 수 있고 이것보다 쉬운 nlogn풀이도 존재합니다.
p.s.2 그니까 저건 나중에 공부해서 포스팅할게요. 이거하는데도 지침 + sa와 한쌍인 lcp알고리즘도 다음에... 저가 너무 멍청해서
======================================================
이전 블로그에 있던 글 옮겨왔습니다. ㅎ
'Problem Solving > 이론' 카테고리의 다른 글
| nCr mod p 구하기 (2) | 2018.04.26 |
|---|---|
| 거듭 제곱의 합 (2) | 2016.10.22 |