Funcia
Lv.3kmpstringz-algorithm

문자열의 모든 주기

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

길이 NN인 문자열 s가 주어집니다. 1≤p≤N1 \le p \le N인 정수 pp가 다음을 만족하면 pp를 s의 주기라고 합니다.

0≤i<N−p0 \le i < N - p인 모든 ii에 대해 s[i] = s[i + p]

즉 s를 pp칸 밀어서 겹쳐 보았을 때 겹치는 부분이 모두 같다는 뜻입니다. p=Np = N이면 겹치는 부분이 없으므로 항상 주기입니다.

s의 모든 주기를 오름차순으로 담은 배열을 반환하세요.

입출력 예

sresult
"abaababa"[5, 7, 8]
"aaaa"[1, 2, 3, 4]
"abcabcab"[3, 6, 8]

입출력 예 설명

예 1 — p=5p = 5일 때 s[0..2] = "aba"와 s[5..7] = "aba"가 같습니다. p=7p = 7이면 s[0] = s[7] = 'a'입니다. 1~4, 6은 주기가 아닙니다.

예 2 — 모든 글자가 같으므로 어떤 pp든 주기입니다.

예 3 — "abc"가 반복되므로 3과 6이 주기이고, 8은 항상 주기입니다.

효율성

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

함수 시그니처

solution(s: string) → int[]

제한 사항

  • 1≤N=1 \le N = s.length ≤500,000\le 500{,}000
  • s는 알파벳 소문자로만 이루어져 있습니다.

기대 복잡도

시간
O(N)
공간
O(N)

입출력 예

s기대 출력
"abaababa"[5,7,8]
"aaaa"[1,2,3,4]
"abcabcab"[3,6,8]

힌트

힌트

pp가 주기라는 것은 s[p..]가 s의 접두사와 같다는 뜻입니다. 즉 위치 pp에서 시작하는 접미사와 s 전체의 가장 긴 공통 접두사 길이가 N−pN - p이면 pp는 주기입니다.

이 값을 모든 위치에 대해 한 번에 구하는 것이 Z 알고리즘입니다. z[i]는 s와 s[i..]의 가장 긴 공통 접두사 길이이며, 이미 찾아 둔 구간 [l, r) 안의 정보를 재활용해 전체를 O(N)O(N)에 계산합니다.

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인 모든 pp와 NN입니다. (KMP의 실패 함수로 **경계(border)**를 따라가도 같은 답을 얻습니다. 길이 bb인 경계가 있으면 N−bN - b가 주기입니다.)

복잡도 목표

pp마다 겹치는 부분을 직접 비교하는 풀이는 "aaaa…" 같은 문자열에서 O(N2)O(N^2)이 되어 효율성 테스트에서 시간 초과가 납니다.

언어별 시간 제한

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

테스트 그룹

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

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