[Platinum II] 문자열의 주기 예측 - 1787

문제 링크

성능 요약

메모리: 127040 KB, 시간: 6876 ms

분류

다이나믹 프로그래밍, 문자열, KMP

제출 일자

2025년 9월 30일 16:19:39

문제 설명

알파벳 소문자들로만 이루어진 문자열을 생각하자. 이런 문자열을 읽어 나가다 보면, 문자열의 주기가 예측되는 순간이 있다. 다음과 같은 문자열을 예로 들어 보자.

a b a b a b a

이 문자열을 네 번째 문자까지의 문자열 'a b a b'와, 그 뒤에 남은 'a b a'로 나누어 생각해 볼 수 있다. 이렇게 하면 뒤쪽 문자열은 앞쪽 네 개의 문자 중 세 번째 문자까지가 반복되다가 끝나는 꼴이다.

a b a b a b a

또한, 여섯 번째 문자까지의 문자열 'a b a b a b'와, 그 뒤에 남은 'a'로 나누어서 생각할 수도 있다. 이 경우에도 뒤쪽 문자열은 앞쪽 문자열이 반복되다가 끝나는 꼴이다.

즉, 예시된 문자열은 'a b a b'혹은, 'a b a b a b'가 반복되는 문자열의 일부라고 예상할 수 있는 것이다. 단, 이러한 추정에서 뒤쪽 문자열이 앞쪽 문자열보다 길면 안 된다. 예를 들어 'a b'는 이 문자열의 주기로 예측하기에는 너무 짧다.

이제는 어떤 문자열 S에 대해, 첫 번째 문자부터, i번째 문자까지로 이루어진 부분 문자열 S_i를 생각해 보자. 모든 각각에 대해, 위에 예시된 것처럼 문자열의 주기를 추정할 수 있다. 우리가 관심 있는 것은 이렇게 각각에 S_i에 대해 추정할 수 있는 주기 중 가장 긴 것의 길이이다. 이를 P_i라고 하자. 예시된 문자열에서 P₇은 4와 6중 최댓값인 6이 된다.

길이가 n인 문자열 S가 주어졌을 때, P₁ + P₂ + ... + P_n을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 문자열 S의 길이 n이 주어진다. (1 ≤ n ≤ 1,000,000) 둘째 줄에 문자열 S가 공백 없이 주어진다.

출력

첫째 줄에, P₁ + P₂ + ... + P_n의 값을 출력한다.

---

💡 해결 방법

💻 코드

# https://www.acmicpc.net/problem/1787
 
import sys
input = sys.stdin.readline
 
def kmp(all_string, pattern):  
    table = [0 for _ in range(len(pattern))]
    i = 0
    for j in range(1, len(pattern)):
        while i > 0 and pattern[i] != pattern[j]:
            i = table[i - 1]
        if pattern[i] == pattern[j]:
            i += 1
            table[j] = i
            
    return table
 
 
n = int(input())
s = input().strip()
 
ans = kmp(s,s)
 
 
result = 0
 
dp = [-1] * n
for i in range(len(ans)):
    if  dp[i] == -1:
        dp[i] = ans[i]
    
    r = dp[i]
    
    while 1:
        if r - 1 >= 0 and ans[r -1] > 0:
            if dp[r - 1] == -1:
                dp[r - 1] = ans[r - 1]
                
            r = dp[r - 1]
                
        else:
            break
    if r > 0:
        result += (i + 1 - r)
    
print(result)