문자열의 모든 주기
- 메모리 제한
- 256 MB
- 정확성 시간 제한
- 10000 ms
- 푼 사람
- 0
길이 인 문자열 s가 주어집니다. 인 정수 가 다음을 만족하면 를 s의 주기라고 합니다.
인 모든 에 대해
s[i] = s[i + p]
즉 s를 칸 밀어서 겹쳐 보았을 때 겹치는 부분이 모두 같다는 뜻입니다. 이면 겹치는 부분이 없으므로 항상 주기입니다.
s의 모든 주기를 오름차순으로 담은 배열을 반환하세요.
입출력 예
| s | result |
|---|---|
"abaababa" | [5, 7, 8] |
"aaaa" | [1, 2, 3, 4] |
"abcabcab" | [3, 6, 8] |
입출력 예 설명
예 1 — 일 때 s[0..2] = "aba"와 s[5..7] = "aba"가 같습니다. 이면 s[0] = s[7] = 'a'입니다. 1~4, 6은 주기가 아닙니다.
예 2 — 모든 글자가 같으므로 어떤 든 주기입니다.
예 3 — "abc"가 반복되므로 3과 6이 주기이고, 8은 항상 주기입니다.
효율성
이 문제에는 효율성 테스트가 있습니다. 제한 사항의 입력 크기를 보고 필요한 시간 복잡도를 직접 판단하세요.
함수 시그니처
solution(s: string) → int[]
제한 사항
-
s.length s는 알파벳 소문자로만 이루어져 있습니다.
기대 복잡도
- 시간
- O(N)
- 공간
- O(N)
입출력 예
| s | 기대 출력 |
|---|---|
"abaababa" | [5,7,8] |
"aaaa" | [1,2,3,4] |
"abcabcab" | [3,6,8] |
힌트
힌트
가 주기라는 것은 s[p..]가 s의 접두사와 같다는 뜻입니다. 즉 위치 에서 시작하는 접미사와 s 전체의
가장 긴 공통 접두사 길이가 이면 는 주기입니다.
이 값을 모든 위치에 대해 한 번에 구하는 것이 Z 알고리즘입니다. z[i]는 s와 s[i..]의 가장 긴 공통 접두사 길이이며,
이미 찾아 둔 구간 [l, r) 안의 정보를 재활용해 전체를 에 계산합니다.
l = r = 0
for i in 1 .. N-1:
z[i] = min(r - i, z[i - l]) if i < r else 0
while i + z[i] < N and s[z[i]] == s[i + z[i]]: z[i] += 1
if i + z[i] > r: l, r = i, i + z[i]
답은 z[p] == N - p인 모든 와 입니다. (KMP의 실패 함수로 **경계(border)**를 따라가도 같은 답을 얻습니다. 길이 인 경계가 있으면 가 주기입니다.)
복잡도 목표
마다 겹치는 부분을 직접 비교하는 풀이는 "aaaa…" 같은 문자열에서 이 되어 효율성 테스트에서 시간 초과가 납니다.
언어별 시간 제한
| 언어 | 효율성 시간 제한 | |
|---|---|---|
| C (GCC, gnu17) | 200 ms | 추정 |
| C++ (GCC, gnu++23) | 200 ms | 도출됨 |
| Python 3.13 | 1000 ms | 도출됨 |
| Java 25 | 1192 ms | 도출됨 |
| Kotlin 2.4 (JVM) | 1400 ms | 추정 |
| C# 14 (.NET 10) | 1400 ms | 추정 |
테스트 그룹
| 그룹 | 배점 | 테스트 수 | 공개 범위 |
|---|---|---|---|
| sample | 0 | 3 | 입력·출력 공개 |
| correctness | 40 | 12 | 판정만 |
| performance | 60 | 4 | 판정만 |