위 포스트는 백준 1787 - 문자열의 주기 예측 의 해설입니다.

핵심 아이디어#

결국 부분 문자열에서 가장 짧으면서 일치하는 Prefix와 Suffix를 찾으면 된다. (해당 길이를 전체 부분문자열 길이에서 뺀 것이 정답이다.)
KMP 알고리즘의 Pi 배열을 이용해보자.

pi[i] := 0~i 부분 문자열에서 prefix와 suffix가 일치하면서 가장 긴 길이
이때, 우리는 가장 짧은 prefix와 suffix를 찾는데 이를 재귀적으로 해결할 수 있다.

이렇게 있을 때 pre와 suf는 일치한다. 따라서 pre의 pi 배열 길이만큼이 suf의 뒤에서 pi 배열 길이만큼에 일치한다는 사실을 이용해서 재귀적으로 해결할 수 있다.

따라서 재귀적으로 들어가면서 가장 작은 값을 체크해주면 된다.

코드#

cpp
1#include <bits/stdc++.h>
2
3#define endl "\n"
4#define all(v) (v).begin(), (v).end()
5#define all1(v) (v).begin()+1, (v).end()
6#define For(i, a, b) for(int i=(a); i<(b); i++)
7#define FOR(i, a, b) for(int i=(a); i<=(b); i++)
8#define Bor(i, a, b) for(int i=(a)-1; i>=(b); i--)
9#define BOR(i, a, b) for(int i=(a); i>=(b); i--)
10#define ft first
11#define sd second
12
13using namespace std;
14using ll = long long;
15using lll = __int128_t;
16using ulll = __uint128_t;
17using ull = unsigned long long;
18using ld = long double;
19using pii = pair<int, int>;
20using pll = pair<ll, ll>;
21using ti3 = tuple<int, int, int>;
22using tl3 = tuple<ll, ll, ll>;
23
24template<typename T> using ve = vector<T>;
25template<typename T> using vve = vector<vector<T>>;
26
27template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
28template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
29
30const int INF = 987654321;
31const int INF0 = numeric_limits<int>::max();
32const ll LNF = 987654321987654321;
33const ll LNF0 = numeric_limits<ll>::max();
34
35int n;
36string s;
37ve<int> dp, pi;
38
39vector<int> getPi(string p){
40    int m = (int)p.size(), j=0;
41    vector<int> ret(m, 0);
42    for(int i=1; i<m; i++){
43        while(j > 0 && p[i] != p[j]) j = ret[j-1];
44        if(p[i] == p[j]) ret[i] = ++j;
45    }
46    return ret;
47}
48int sol(int i) {
49    if(i<0) return INF;
50    int &ret = dp[i];
51    if(ret != -1) return ret;
52    if(!pi[i]) return ret = INF;
53    return ret = min(pi[i], sol(pi[i]-1));
54}
55
56void solve() {
57    cin >> n >> s;
58    pi = getPi(s);
59    dp = ve<int>(n, -1);
60
61    ll ans = 0;
62    for(int i=0; i<n; i++) {
63        ll res = sol(i);
64        if(res != INF) ans += i+1 - res;
65    }
66    cout << ans << endl;
67}
68
69int main(void) {
70    ios_base::sync_with_stdio(false);
71    cin.tie(nullptr);
72    cout.tie(nullptr);
73
74    int TC=1;
75//    cin >> TC;
76    FOR(tc, 1, TC) {
77//        cout << "Case #" << tc << ": ";
78        solve();
79    }
80
81
82    return 0;
83}

참고#

https://justicehui.github.io/poi/2020/05/09/BOJ1787/