[c++] 백준 11478- 서로 다른 부분 문자열의 개수(접미사 배열의 활용)

0. [c++] 백준  -

https://www.acmicpc.net/problem/11478

1. 풀이

이전에 접미사 배열을 그대로 활용하여 해결해야 하는 문제이다.

이 문제에서 풀어야 하는 문제는 반복이 없는 문자열의 개수를 구하는 것인데, 신기하게도 N의 길이의 문자열이 있으면

N(N+1)/2 (N의 길이로 만들 수 있는 전체 문자열) 에 LCP Array의 총 합을 빼주면 정답이 나온다.

조금 생각해보니, LCP Array의 총 합을 빼는 것은, 반복되는 문자열을 빼주는 것과 동일하다는 것을 알게되었다.

baaa라는 문자열이 주어졌다 가정해보자.

만들 수 있는 총 문자열은

baaa             1

baa aaa         2

ba aa (aa)      2 (+1)

b a (a) (a)      2 (+2)

이로코롬 되는데 이는 4*5/2 에서 3만큼 빼준 결과값이 된다.

이때, 이 문자열로 만들 수 있는 suffix Array는 아래와 같다.

a

aa

aaa

baaa

이때 최대 공통 부분 수열은

1,2,0으로 위의 결과와 동일함을 볼 수 있다.

더 깊은 설명은 귀찮으니 생략....

대충 생각해보면, N*(N+1)/2 의 유도과정이 LCP Array를 더하는 것과 동일한 과정이여서 결과적으로 동일한 결과값을 구해 낼 수 있게 된 것이다.

2. 소스코드

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 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72

#include<iostream> #include<algorithm> #include<string> #include<vector>   using namespace std;   const int MAX = 1001;   string S; int suffixArray[MAX], pos[MAX], LCPArray[MAX]; int temp[MAX]; int T, N;   bool cmp(int i, int j) {     //먼저 자신의 위치의 문자를 비교     if (pos[i] != pos[j]) return pos[i] < pos[j];     //문자가 같으면 T칸 뒤의 문자끼리 비교     i += T;     j += T;     return (i < N && j < N) ? (pos[i] < pos[j]) : (i > j); }   //S를 사용해 suffixArray를 만드는 함수 void constructSuffixArray() {     N = S.size();     for (int i = 0; i < N; i++) {         suffixArray[i] = i;         pos[i] = S[i];     }     //T를 2배씩 늘려가면서 매번 앞에서 부터 T*2글자만 보고 접미사 정렬     for (T = 1; T <=N; T *= 2) {         sort(suffixArray, suffixArray + N, cmp);         temp[0] = 0;         //앞에서부터 훑으면서 각 접미사가 서로 다른 그룹에 속할 때마다 그룹 번호 증가         for (int i = 0; i < N - 1; i++)             temp[i + 1] = temp[i] + cmp(suffixArray[i], suffixArray[i + 1]);         //pos배열을 temp배열로 대체         for (int i = 0; i < N; i++)             pos[suffixArray[i]] = temp[i];           //모든 접미사가 다른 그룹으로 나뉘어졌다면 종료         if (temp[N - 1] == (N - 1))             break;     } }   void makeLCPArray() {     int N = S.size();     for (int i = 0, k=0; i < N; i++, k = max(k-1, 0)) {         //배열 중 마지막 위치의 문자는 계산 불가         if (pos[i] == N - 1) continue;                  for (int j = suffixArray[pos[i] + 1]; S[i + k] == S[j + k]; k++);         LCPArray[pos[i]] = k;     } }         int main() {     cin >> S;     constructSuffixArray();     int ret = 0;     for (int i = 0; i < N; i++)         ret += suffixArray[i] + 1;     makeLCPArray();     for (int i = 0; i < N - 1; i++)         ret -= LCPArray[i];     cout << ret; } Colored by Color Scripter

cs

3. 참고

https://blog.naver.com/PostView.nhn?blogId=kks227&logNo=221028710658

질문이나 지적 있으시면 댓글로 남겨주세요~

도움 되셨으면 하트 꾹!