백준 1498 - 주기문
Updated:
Categories: Problem Solving
주기문
풀이
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이 된다.
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#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;
}
Leave a comment