[백준] 4354 - 문자열 제곱 (c++)

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

 

문제 요약

문자열 x가 있을 때 x를 n번 반복한 형태를 x^n라고 표현한다. 

문자열 s가 주어졌을 때 s=x^n이 성립하는 최대 n을 구해라.

 

풀이 (N)

• KMP

최소 반복 주기를 구하기 위해 KMP의 실패함수를 활용할 수 있다.

n이 최대이고 1보다 큰 경우를 생각해보자. s="ababab"="ab"^3을 예로 들면 s의 실패함수 마지막 값이 "abab" 즉 "ab"^(n-1)이 된다. (n-실패함수 마지막 값)이 최소 주기이고 s/최소 주기가 답이 된다.

s%주기>=1 이라면 답은 1이다. s%최소 주기>=1 && n>1인 문자열이 없기 때문이다.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define mid (st+en>>1)

int main() {
    cin.tie(0)->sync_with_stdio(0);
    while(1) {
        string s;cin>>s;
        int n=s.size();
        if(s==".")
            break;
        
        vector<int> f(n),ans;
        for(int i=1,j=0;i<n;i++) {
            while(j>0&&s[i]!=s[j]) j=f[j-1];
            if(s[i]==s[j])f[i]=++j;
        }

        int m=n-f[n-1];
        
        cout<<(n%m?1:n/m)<<'\n';
    }
}