문자열 s가 주어졌을 때, 이 문자열과 자기 자신의 모든 접미사(suffix) 사이의 유사도 합계를 구하는 문제입니다. 여기서 두 문자열 간의 유사도란 두 문자열이 공통으로 가지는 가장 긴 접두사(prefix)의 길이를 의미합니다.
문제 예시
입력이 s = "pqpqpp"라고 가정해 보겠습니다. 이 문자열의 접미사는 "pqpqpp", "qpqpp", "pqpp", "qpp", "pp", "p"로 총 6개이며, 각 접미사와 원본 문자열 "pqpqpp"의 유사도는 순서대로 6, 0, 3, 0, 1, 1입니다. 따라서 전체 합계는 다음과 같습니다.
6 + 0 + 3 + 0 + 1 + 1 = 11
풀이 접근 방법
이 문제는 Z-알고리즘(Z-algorithm)의 아이디어를 응용하면 효율적으로 해결할 수 있습니다. Z-알고리즘은 문자열의 각 위치에서 시작 부분과 일치하는 최장 접두사 길이를 선형 시간 O(n) 안에 계산하는 알고리즘으로, 이미 계산된 일치 구간 [l, r] 정보를 재활용해 불필요한 문자 비교를 줄이는 것이 핵심입니다.
구체적인 절차는 다음과 같습니다.
- length := 문자열 s의 길이
- total := length (첫 번째 접미사는 문자열 자신이므로 유사도는 length)
- z := 0으로 초기화된 리스트
- l := 0, r := 0 (지금까지 발견된 가장 오른쪽 일치 구간)
- k를 1부터 length-1까지 반복합니다.
- k > r인 경우(기존 구간 밖): match := 0, index := k로 설정한 뒤 문자를 하나씩 비교하며 match를 계산하고 z에 추가합니다. match > 0이면 total에 더하고 l, r을 갱신합니다.
- k ≤ r인 경우(기존 구간 안):
- z[k-l] < (r-k)+1이면: 이미 계산된 값 z[k-l]을 그대로 사용해 z에 추가하고 total에 더합니다.
- 그렇지 않으면: match := r-k, index := r부터 문자 비교를 이어가며 match를 확장한 후 z에 추가하고 total에 더한 뒤 l, r을 갱신합니다.
- 반복이 끝나면 total을 반환합니다.
파이썬 구현 예제
다음 구현을 통해 더 잘 이해해 보겠습니다.
def solve(s):
length = len(s)
total = length
z = [0]
l = 0
r = 0
for k in range(1, length):
if k > r:
match = 0
index = k
while index < length:
if s[index] == s[match]:
match += 1
index += 1
else:
break
z.append(match)
if match > 0:
total += match
l = k
r = index - 1
else:
if z[k-l] < (r-k)+1:
z.append(z[k-l])
total += z[k-l]
else:
match = r-k
index = r
while index < length:
if s[index] == s[match]:
match += 1
index += 1
else:
break
z.append(match)
total += match
l = k
r = index - 1
return total
s = "pqpqpp"
print(solve(s))입력
"pqpqpp"
출력
11
시간 및 공간 복잡도
이 알고리즘은 각 문자를 최대 상수 번만 비교하므로 시간 복잡도는 O(n), Z 배열 저장을 위한 공간 복잡도 역시 O(n)입니다. 모든 접미사를 처음부터 일일이 비교하는 단순한 방식(O(n²))보다 훨씬 효율적이며, 문자열이 길어질수록 그 성능 차이가 커집니다.