[백준/C++] 4354번 문자열 제곱

https://www.acmicpc.net/problem/4354

4354번: 문자열 제곱

이 문제를 보고, '반복 가능한 최소 길이의 부분 문자열' 을 찾으면 될 것 같았다. 없으면 1 출력해주고

어떻게 찾을까 고민하던 중, 실패함수의 마지막 값은 문자열 전체를 봤을 때의 최장 부분 문자열을 구한 것이므로 내가 찾고자 하는            '반복 가능한 최소 길이의 부분 문자열'의 길이는 전체 문자열 - 실패함수의 마지막 값을 통해 구할 수 있다!

그래서 전체 문자열 길이 / '반복 가능한 최소 길이의 부분 문자열'의 길이를 해주면 답이 되는데,,,

여기서 한가지 문제가 있다. 우리는 나눗셈을 진행해주는데, 딱 나눠떨어지지 않는 경우가 반드시 존재할 것 같다.

나누어 떨어지지 않는 경우는, 반복이 가능한 부분 문자열이 없다는 뜻과 동일하게 볼 수 있다. 1을 출력해주자.

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

vector<int> failure(string str){
    int j=0;
    int siz = str.length();
    vector<int> fail(str.length());
    // pi 배열은 접두사 접미사가 일치하는 최대 길이 구하기
    for(int i = 1; i < siz; i++){
        while(j > 0 && str[i] != str[j]) { // 다르면
            j = fail[j - 1]; // 일치하는 부분까지 인덱스를 앞당김
        }
        if(str[i] == str[j]) {
            fail[i] = ++j; // 접두 접미사가 일치하는 최대 길이 저장
        }
        else{
            fail[i]=0;
        }
    }
    return fail;
}

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

    string s;
    while(true){
        cin >> s;
        if(s==".") break;
        vector<int> f = failure(s);

        if(s.size()%(s.size()-f[s.size()-1]))
            cout << 1<<'\n';
        else
            cout << s.size() / (s.size() - f[s.size() - 1]) << '\n';
    }

    return 0;
}