모든 접두사의 경계 합
플래티넘 V의견: 0
문자열 \(S\) 가 주어진다. \(S\) 의 각 접두사 \(S[1..i]\) (\(1 \le i \le |S|\)) 에 대해, 그 접두사의 가장 긴 진(proper) 경계(border) 의 길이를 \(b_i\) 라 하자.
경계란, 어떤 접두사이면서 동시에 접미사인 문자열이며, 진 경계는 자기 자신을 제외한 것을 말한다. (\(i=1\) 이면 진 경계가 없어 \(b_1 = 0\).)
다음 합을 구하여라.
$$ \sum_{i=1}^{|S|} b_i $$
\(b_i\) 의 값들은 정확히 KMP 실패 함수 \(\pi[i]\) 와 같으므로, 실패 함수를 \(O(|S|)\) 에 계산하여 모두 더하면 된다. 합이 클 수 있으니 64비트 정수를 사용하라.
\(1 \le |S| \le 1{,}000{,}000\)
\(S\) 는 알파벳 소문자로만 이루어져 있다.
첫째 줄에 알파벳 소문자로 이루어진 문자열 \(S\) 가 주어진다.
모든 접두사의 최장 진 경계 길이의 합을 출력한다.
abacaba
7abacaba 의 각 접두사 최장 진 경계: a→0, ab→0, aba→1, abac→0, abaca→1, abacab→2, abacaba→3. 합은 \(0+0+1+0+1+2+3=7\) 이다.
aaaa
6aaaa 의 접두사 경계: 0,1,2,3. 합은 6이다.
riseoj 작성
출처 Original
평가 및 의견
모든 접두사의 경계 합
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
모든 접두사의 경계 합