Funcia
Lv.3binary-searchhashingrolling-hashstring

두 번 나타나는 가장 긴 부분 문자열

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

문자열 s가 주어집니다. s 안에서 서로 다른 두 위치에서 시작하는 같은 부분 문자열(연속한 구간) 중 가장 긴 것의 길이를 반환하세요. 두 등장 위치는 겹쳐도 됩니다. 두 번 이상 나타나는 부분 문자열이 없으면 0을 반환합니다.

입출력 예

sresult
"banana"3
"abcd"0
"aaaaa"4

입출력 예 설명

예 1 — "ana"가 위치 1과 3에서 나타납니다(두 등장은 겹칩니다). 길이 4 이상은 두 번 나타나는 것이 없습니다.

예 2 — 모든 글자가 달라 길이 1짜리도 두 번 나타나지 않습니다.

예 3 — "aaaa"가 위치 0과 1에서 나타납니다.

효율성

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

함수 시그니처

solution(s: string) → int

제한 사항

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

기대 복잡도

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

입출력 예

s기대 출력
"banana"3
"abcd"0
"aaaaa"4

힌트

힌트

길이 LL짜리가 두 번 나타나면 그보다 짧은 길이도 두 번 나타납니다(앞부분만 잘라 보면 됩니다). 따라서 "길이 LL인 부분 문자열이 두 번 나타나는가?"에 대해 이분 탐색을 할 수 있습니다.

길이 LL을 확인할 때는 모든 길이 LL 구간을 롤링 해시로 O(1)O(1)씩 구해 집합(또는 정렬)으로 중복을 찾습니다.

H(i,L)=h[i+L]−h[i]⋅BL(modM),h[i+1]=h[i]⋅B+s[i]H(i, L) = h[i + L] - h[i] \cdot B^{L} \pmod M, \qquad h[i+1] = h[i] \cdot B + s[i]

해시 충돌을 줄이려면 261−12^{61} - 1 같은 큰 소수를 모듈로 쓰거나, 서로 다른 모듈로 두 개를 함께 쓰세요. (접미사 배열과 LCP 배열로 풀 수도 있습니다.)

복잡도 목표

모든 위치 쌍(또는 모든 이동 거리)을 직접 비교하는 O(N2)O(N^2) 풀이는 효율성 테스트에서 시간 초과가 납니다. O(Nlog⁡N)O(N \log N)이 필요합니다.

언어별 시간 제한

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

테스트 그룹

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

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