본문 바로가기

알고리즘 관련/BOJ

BOJ)4354 문자열 제곱

문제: icpc.me/4354


문자열 A가 주어질 때, A를 서로 같은 부분 문자열 N개로 쪼갤 수있을 때 N의 최댓값을 출력하는 문제다.


우리는 문자열이 N개의 부분 문자열로 쪼개질 때 규칙성을 찾아보면 


KMP에서의 pi배열의 pi[a.length()-1]=(n-1/n)*a.length()를 만족한다는 걸 알 수 있다.


이를 이용하여 최대 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
#include <cstdio>
#include <algorithm>
#include <string>
#include <iostream>
#include <vector>
using namespace std;
string a;
vector<int> pi;
void getpi(){
    pi.clear();
    pi.resize(a.length());
    int j = 0;
    for (int i = 1; i < a.length(); i++){
        while (j > && a[i] != a[j])
            j = pi[j - 1];
        if (a[i] == a[j])
            pi[i] = ++j;
    }
}
int main() {
    while (1) {
        cin >> a;
        if (a == ".")
            break;
        getpi();
        for (int i = a.length(); i > 0; i--) {
            if (pi[a.length() - 1== (double)((double)(i - 1/ i)*(double)a.length()) {
                printf("%d\n", i);
                break;
            }
        }
    }
    return 0;
}
cs


'알고리즘 관련 > BOJ' 카테고리의 다른 글

BOJ)1701 Cubeditor  (0) 2017.02.01
BOJ)11585 속타는 저녁 메뉴  (0) 2017.02.01
BOJ)4354 문자열 제곱  (0) 2017.02.01
BOJ)2233 사과나무  (0) 2017.02.01
BOJ)3682 동치 증명  (0) 2017.01.31
BOJ)11338 XOR Sum  (0) 2017.01.31

태그