티스토리 뷰

알고리즘 관련/BOJ

BOJ)4354 문자열 제곱

JASON 자손9319 2017. 2. 1. 21:22

문제: 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
TAG
댓글
댓글쓰기 폼