[백준][C++]11478번. 서로 다른 부분 문자열의 개수

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

 

 

처음에 봤을 때 부분 문자열의 조합을 이중반복문을 통해 구하고 이를 set 자료형을 통해 하나씩 넣고 마지막에 그 크기를 출력해주는 것으로 생각했다. 이렇게 풀어도 정답이 된다. 

 

정답코드1(반복문 사용)

#include <iostream>
#include <set>

using namespace std;

set<string> s;
int main()
{
	string word;

	cin >> word;

	//부분 문자열 시작위치
	for (int i = 0; i < word.size(); i++)
	{
		string w = "";
		for (int j = i; j < word.size(); j++)		//부분 문자열 길이
		{
			w += word[j];
			s.insert(w);
		}
	}

	cout << s.size() << endl;
}

 

하지만 더 최적화해보자면 접미사 배열 (Suffix Array) 이라는 것을 사용해서 풀면 된다. 

이때 접미사 배열은 문자열 s의 모든 접미사를 사전 순으로 정렬한 것으로 각 접미사가 문자열에서 시작하는 인덱스를 기준으로 정렬 한다. 예시 입력을 바탕으로 보자면 

s의 접미사 목록:

1. s[0:] = "ababc"
2. s[1:] = "babc"
3. s[2:] = "abc"
4. s[3:] = "bc"
5. s[4:] = "c"

이런식으로 접미사가 만들어진다.

여기서 중복되는 부분 문자열을 제거하기 위해 접미사 배열을 활용한 LCP 배열이라는 것을 사용하게 되는데 이는 은 접미사 배열의 인접한 접미사들 간에 겹치는 접두사의 길이를 저장한 배열이다. 

인접한 접미사들 간의 공통 접두사:

1. "ababc"와 "abc"의 공통 접두사: "ab" → 길이 2
2. "abc"와 "babc"의 공통 접두사: 없음 → 길이 0
3. "babc"와 "bc"의 공통 접두사: "b" → 길이 1
4. "bc"와 "c"의 공통 접두사: 없음 → 길이 0

이렇게 되면 LCP배열은  [2, 0, 1, 0] 이런식으로 만들어 진다. 

이제 중복되는 것을 포함한 전체 부분 문자열의 개수를 구해준 다음 중복되는 수를 빼주면 된다. 

부분 문자열의 개수는 n(n+1) /2 로 계산할 수 있다. 

이를 코드로 구현하면 다음과 같다.

 

 

정답코드2(접미사 배열활용)

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

using namespace std;

// 접미사 배열 구하기
vector<int> build_suffix_array(const string& s) {
    int n = s.size();
    vector<int> suffix_array(n), rank(n), temp(n);

    // 초기 순위 설정 (문자의 아스키 값에 따른 정렬)
    for (int i = 0; i < n; i++) {
        suffix_array[i] = i;
        rank[i] = s[i];
    }

    // 접미사 길이 1, 2, 4, 8...씩 늘려가며 정렬
    for (int len = 1; len < n; len *= 2) {
        auto cmp = [&](int i, int j) {
            if (rank[i] != rank[j]) return rank[i] < rank[j];
            int ri = (i + len < n) ? rank[i + len] : -1;
            int rj = (j + len < n) ? rank[j + len] : -1;
            return ri < rj;
        };
        sort(suffix_array.begin(), suffix_array.end(), cmp);

        // 임시 순위 갱신
        temp[suffix_array[0]] = 0;
        for (int i = 1; i < n; i++) {
            temp[suffix_array[i]] = temp[suffix_array[i - 1]] + cmp(suffix_array[i - 1], suffix_array[i]);
        }
        rank = temp;
    }
    return suffix_array;
}

// LCP 배열 구하기
vector<int> build_lcp_array(const string& s, const vector<int>& suffix_array) {
    int n = s.size();
    vector<int> rank(n), lcp(n);

    for (int i = 0; i < n; i++) {
        rank[suffix_array[i]] = i;
    }

    int h = 0;
    for (int i = 0; i < n; i++) {
        if (rank[i] > 0) {
            int j = suffix_array[rank[i] - 1];
            while (i + h < n && j + h < n && s[i + h] == s[j + h]) {
                h++;
            }
            lcp[rank[i]] = h;
            if (h > 0) h--;
        }
    }
    return lcp;
}

// 서로 다른 부분 문자열 개수 구하기
int count_unique_substrings(const string& s) {
    int n = s.size();

    // 접미사 배열과 LCP 배열 생성
    vector<int> suffix_array = build_suffix_array(s);
    vector<int> lcp = build_lcp_array(s, suffix_array);

    int total_substrings = n * (n + 1) / 2;  // 모든 부분 문자열의 개수
    int lcp_sum = 0;  // LCP들의 합

    for (int i = 1; i < n; i++) {
        lcp_sum += lcp[i];  // LCP 값의 합
    }

    return total_substrings - lcp_sum;  // 전체 부분 문자열에서 중복된 부분을 빼기
}

int main() {
    string s;
    cin >> s;

    int result = count_unique_substrings(s);
    cout << result << endl;

    return 0;
}

 

확실히 공간,시간 복잡도가 확연히 줄어든 모습을 볼 수있다. 이론은 이해할 수 있었지만 이를 구현하기는 어렵지만 최적화가 필요할 때는 이 방법을 활용하면 좋을 것같다.