백준 1498 - 주기문

주기문

풀이

KMP 알고리즘의 pi 배열을 이용한다.

길이가 a인 문자열의 pi[a]를 b라 하자.
[ [------b------][--(a-b)--] ] 이런 식으로 문자열 a가 있다고 하자.
만약 a를 (a-b)로 나눴을 때 나눠 떨어진다면 문자열 a는 (a-b) 문자열의 반복으로 이루어져 있다.
그 이유는 a가 (a-b)로 나눠진다는 건 b 또한 (a-b) 덩어리들로 나눌 수 있다는 거고 prefix인 b는 문자열 a의 suffix와 동일하기 때문에 결국 a-b 문자열이 반복된다는 사실을 알 수 있다.

따라서 a / (a-b)가 해당 문자열 a의 가장 큰 n이 된다.

코드

#include <bits/stdc++.h>

#define endl "\n"
#define all(v) (v).begin(), (v).end()
#define For(i, a, b) for(ll i=(a); i<(b); i++)
#define FOR(i, a, b) for(ll i=(a); i<=(b); i++)
#define Bor(i, a, b) for(ll i=(a); i>(b); i--)
#define BOR(i, a, b) for(ll i=(a); i>=(b); i--)
#define ft first
#define sd second

using namespace std;
using ll = long long;
using lll = __int128_t;
using ulll = __uint128_t;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using ti3 = tuple<int, int, int>;
using tl3 = tuple<ll, ll, ll>;

template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }

const int INF = 987654321;
const int INF0 = numeric_limits<int>::max();
const ll LNF = 987654321987654321;
const ll LNF0 = numeric_limits<ll>::max();

vector<int> getPi(string &p){
    int m = (int)p.size(), j=0;
    vector<int> pi(m, 0);
    for(int i=1; i<m; i++){
        while(j > 0 && p[i] !=  p[j])
            j = pi[j-1];
        if(p[i] == p[j])
            pi[i] = ++j;
    }
    return pi;
}
vector<int> pi;

void solve() {
    string s; cin >> s;
    pi = getPi(s);

    For(i,1,s.length()) {
        if(pi[i] == 0) continue;
        int a = i+1, a_b = i+1-pi[i];
        if(a%a_b == 0) cout << i+1 << ' ' << a/a_b << endl;
    }
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int TC=1;
//    cin >> TC;
    FOR(tc, 1, TC) {
//        cout << "Case #" << tc << ": ";
        solve();
    }


    return 0;
}