백준 4354 문자열 제곱 c++ (kmp)

문제 출처 : www.acmicpc.net/problem/4354

4354번: 문자열 제곱

문제

알파벳 소문자로 이루어진 두 문자열 a와 b가 주어졌을 때, a*b는 두 문자열을 이어붙이는 것을 뜻한다. 예를 들어, a="abc", b="def"일 때, a*b="abcdef"이다.

이러한 이어 붙이는 것을 곱셈으로 생각한다면, 음이 아닌 정수의 제곱도 정의할 수 있다.

• a^0 = "" (빈 문자열)
• a^(n+1) = a*(a^n)

문자열 s가 주어졌을 때, 어떤 문자열 a에 대해서 s=a^n을 만족하는 가장 큰 n을 찾는 프로그램을 작성하시오.

입력

입력은 10개 이하의 테스트 케이스로 이루어져 있다. 각각의 테스트 케이스는 s를 포함한 한 줄로 이루어져 있다. s의 길이는 적어도 1이며, 백만글자를 넘지 않는다. 마지막 테스트 케이스의 다음 줄은 마침표이다.

출력

각각의 테스트 케이스에 대해, s=a^n을 만족하는 가장 큰 n을 찾은 뒤 출력한다.

알고리즘 분류

• 문자열
• KMP

풀이

kmp 알고리즘의 실패 함수만 사용하면 되는 문제이다.

입력으로는 문자열 s가 주어지고,

s의 부분 문자열 a를 n제곱(문자열 이어붙이기) 했을 때,

s = a^n을 만족하는 가장 큰 n을 찾는 문제이다.

부분 문자열인 a가 작을수록 n은 커진다.

 

부분 문자열 a로 s의 패턴을 만들 수 있다는 가정 하에,

실패 함수의 배열 pi[pi.size()-1]은 가장 긴 부분 문자열 길이임을 알 수 있다.

이를 이용해, pi.size() - pi[pi.size()-1]는 s = a^n을 만족하는 가장 작은 a의 길이라는 것을 알 수 있다.

 

1.문자열 "abcd"의 pi배열은

   0 0 0 0이고

2.문자열 "aaaa"의 pi 배열은

   0 1 2 3이고

3.문자열 "ababab"의 pi 배열은

   0 0 1 2 3 4이고.

4.문자열 "ababa"의 pi 배열은

   0 0 1 2 3이다.

 

1~3번까지는 위와 같이 풀면 되지만, 4번 같은 경우에는

나누어 떨어지지 않기 때문에, 1을 출력한다.

 

코드

#include<iostream>
#include<string>
#include<vector>
using namespace std;

vector<int> makeTable(string pattern) {
    vector<int> table(pattern.size(), 0);
    int j = 0;
    for (int i = 1; i < table.size(); i++) {
        while (j > 0 && pattern[i] != pattern[j]) {
            j = table[j - 1];
        }

        if (pattern[i] == pattern[j]) {
            table[i] = ++j;
        }
    }

    return table;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    string pattern;
    while (true) {
        cin >> pattern;
        if (pattern.compare(".") == 0)
            break;
        vector<int> table = makeTable(pattern);
        if(pattern.size()%(pattern.size()-table[pattern.size()-1]))
            cout << 1<<'\n';
        else
        cout << pattern.size() / (pattern.size() - table[pattern.size() - 1]) << '\n';
    }


    return 0;
}