서로 다른 부분 문자열의 수

레벨 MC · 코딩 · JavaScript · 목표 시간 45분 · 게시일 2026-11-05

소문자 문자열 s의 비어 있지 않은 부분 문자열(연속된 구간) 가운데 내용이 서로 다른 것이 몇 개인지 구하시오. 예를 들어 "aba"의 부분 문자열은 a, b, ab, ba, aba의 5가지이다.

s의 길이는 최대 100,000이다. 부분 문자열을 모두 만들어 집합에 넣는 방법으로는 시간과 메모리 안에 끝나지 않는다.

예제

solve("aba")
solve("aaaa")
solve("abcd")