문제

문자열 S가 주어졌을 때, S의 서로 다른 부분 문자열의 개수를 구하는 프로그램을 작성하시오.

부분 문자열은 S에서 연속된 일부분을 말하며, 길이가 1보다 크거나 같아야 한다.

예를 들어, ababc의 부분 문자열은 a, b, a, b, c, ab, ba, ab, bc, aba, bab, abc, abab, babc, ababc가 있고, 서로 다른것의 개수는 12개이다.

입력

첫째 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져 있고, 길이는 1,000 이하이다.

출력

첫째 줄에 S의 서로 다른 부분 문자열의 개수를 출력한다.

내 접근

1. 부분 문자열을 어떻게 구하지? 중첩 for 문이 필요할 것 같다.
2. 중첩 for문에서 최초 순회 시 얻은 부분 문자열은 다음 순회에서는 구할 필요가 없으니 문자열의 길이를 l이라고 하면 문자열 s의 모든 부분 문자열을 구할 때 시간 복잡도는 O(l(l + 1) / 2)이 되는건가?
3. 문제에서는 그렇게 얻은 부분 문자열의 개수를 원하니까 std::unordered_set을 쓰자

구현

#include <iostream>
#define IO std::cin.tie(NULL), std::ios_base::sync_with_stdio(false)

#include <unordered_set>

void solve() {
  std::string s;

  std::cin >> s;
  size_t l = s.length();
  std::unordered_set<std::string> unique_str;

  for (size_t i = 0; i < l; i++) {
    for (size_t j = i; j < l; j++) {
      std::string substr = s.substr(i, j - i + 1);
      unique_str.insert(substr);
    }
  }

  std::cout << unique_str.size();
}

int main() {
  IO;
  solve();
  return 0;
}

결과

성공, 메모리 209,864 KB, 시간 540 ms

개선점

계산한 시간 복잡도가 맞았는가?

• 부분 문자열 개수: O(l^2)
• 여기에 std::string substr을 고려하지 않았음
• 시간 복잡도는 O(l^3)이 되버림 -> 문제의 입력 제한 n <= 1000으로 인해 통과할 수 있었음

Suffix Array + LCP

아이디어

• 모든 suffix를 정렬
• 전체 부분 문자열 개수는 n(n+1)2\frac{n(n+1)}{2}2n(n+1)​
• 인접한 suffix 간의 LCP(Longest Common Prefix) 길이를 빼면
  → 중복 제거 완료

복잡도

• 시간: O(n log n)
• 공간: O(n)

핵심 수도 코드

suffixes = all suffixes of S
sort(suffixes)

total = n*(n+1)/2
for i from 1 to n-1:
	total -= LCP(suffixes[i], suffixes[i-1])

언제 좋은가

• 입력이 커질 가능성이 있을 때
• 문자열 문제의 정석적인 해결을 원할 때

Suffix Automaton (SAM)

아이디어

• 문자열의 모든 부분 문자열을 상태 그래프로 압축
• 각 상태가 표현하는 substring 길이 범위를 이용
• 상태마다 len(state)−len(link(state))len(state) - len(link(state))len(state)−len(link(state)) 를 더하면 정답

복잡도

• 시간: O(n)
• 공간: O(n)

build SAM for S answer = 0 for each state:     answer += max_len[state] - max_len[link[state]]

언제 좋은가

• 문자열 알고리즘 숙련도를 올리고 싶을 때
• 대규모 입력이 예상될 때