Funcia
Lv.4lcp-arraystringsuffix-array

서로 다른 부분 문자열의 개수

메모리 제한
256 MB
정확성 시간 제한
10000 ms
푼 사람
0
0

영어 소문자로 이루어진 문자열 s가 주어집니다. s의 비어 있지 않은 연속 부분 문자열 중 서로 다른 것이 몇 개인지 반환하세요.

같은 내용의 부분 문자열이 여러 위치에 나타나도 한 번만 셉니다.

입출력 예

sresult
"abab"7
"aaa"3
"banana"15

입출력 예 설명

예 1 — a, b, ab, ba, aba, bab, abab 일곱 개입니다. a, b, ab는 두 번씩 나타나지만 한 번만 셉니다.

예 2 — a, aa, aaa 세 개입니다.

예 3 — 길이 6인 문자열의 부분 문자열 위치는 21개지만, 중복을 빼면 15개가 남습니다.

효율성

이 문제에는 효율성 테스트가 있습니다. 제한 사항의 입력 크기를 보고 필요한 시간 복잡도를 직접 판단하세요.

함수 시그니처

solution(s: string) → long

제한 사항

  • 1≤N=1 \le N = s.length ≤200,000\le 200{,}000
  • s는 영어 소문자(a~z)로만 이루어져 있습니다.
  • 답이 32비트 정수 범위를 넘을 수 있습니다.

기대 복잡도

시간
O(N log^2 N)
공간
O(N)

입출력 예

s기대 출력
"abab"7
"aaa"3
"banana"15

힌트

힌트

모든 부분 문자열은 어떤 접미사의 접두사입니다. 접미사 s[i..]는 접두사를 N−iN - i개 가지므로 전부 더하면 N(N+1)/2N(N+1)/2이고, 여기서 중복만 빼면 됩니다.

접미사 배열과 LCP

  1. 모든 접미사를 사전 순으로 정렬한 접미사 배열 sa를 만듭니다.
  2. 사전 순으로 이웃한 두 접미사의 최장 공통 접두사 길이 lcp[k]를 구합니다.
  3. 정렬된 순서에서 접미사 sa[k]의 접두사 중 앞 접미사와 겹치는 lcp[k]개는 이미 센 것입니다. 따라서

답=N(N+1)2−∑klcp[k]\text{답} = \frac{N(N+1)}{2} - \sum_k \text{lcp}[k]

만드는 방법

  • 접미사 배열: 길이 1,2,4,…1, 2, 4, \dots 의 접두사 순위를 두 배씩 늘려 가며 (rank[i], rank[i+k]) 쌍으로 정렬합니다(prefix doubling). 정렬을 log⁡N\log N번 하므로 O(Nlog⁡2N)O(N \log^2 N), 기수 정렬을 쓰면 O(Nlog⁡N)O(N \log N)입니다.
  • LCP: Kasai 알고리즘. 원래 문자열 순서로 접미사를 보면 이웃 LCP가 한 번에 최대 1씩만 줄어든다는 성질로 O(N)O(N)에 구합니다.

접미사 오토마톤으로도 풀 수 있습니다(각 상태의 len - link.len 합).

복잡도 목표

접미사를 문자열 비교로 정렬하거나 부분 문자열을 집합에 넣는 풀이는 aaaa… 같은 반복 문자열에서 O(N2)O(N^2) 이상이 되어 시간 초과가 납니다.

언어별 시간 제한

언어효율성 시간 제한
C (GCC, gnu17)204 ms추정
C++ (GCC, gnu++23)204 ms도출됨
Python 3.131832 ms도출됨
Java 251388 ms도출됨
Kotlin 2.4 (JVM)1408 ms추정
C# 14 (.NET 10)1408 ms추정

테스트 그룹

그룹배점테스트 수공개 범위
sample03입력·출력 공개
correctness4012판정만
performance605판정만
에디터 불러오는 중…

아직 결과가 없습니다. 실행 또는 제출하세요.