백준 4354 문자열 제곱 쉬운 풀이 (C++/CPP)

문제링크 : https://www.acmicpc.net/problem/4354

문제 추상화

• 각 문자가 몇번 반복되는지 찾아야함
• 근데 연속해서 반복되어야함, 겹치거나 띄어서 반복되면안됨(일반 KMP와 다름)

아이디어

• 문자열의 앞에서부터 자른다음 연속하는지 확인

  • 앞에서부터 자르는건 약수인지 확인
  • 다음 문자부터 문자열길이 단위만큼 비교
  • 시간복잡도 계산
    • 문자열 자르기 , 약수개수: O(M)
    • 문자열 길이 단위만큼 비교 : O(M)
    • O(M*M) : 1e12 시간초과
  • KMP 사용
    • KMP의 fail 배열 : 해당 인덱스에서 접두사와 접미사가 같은것의 개수
    • 각 문자열의 fail 배열을 구할경우, 마지막 값을 통해 몇번 반복되는지 확인할 수 있음
      • fail배열의 마지막값 : 해당 문자열의 접두사와 접미사가 같은 최대의 길이
      • 전체 문자열의 길이에서 이 최대의 길이뺀 값이 전체 문자열에서 반복하는 문자열
    • 단, 접두사와 접미사가 중간에 겹치는경우(팰린드롬 제외)

시간복잡도 계산

• 모든 문자열에 대해서 O(10)
• fail 함수 구함 : O(M)
• 합 : O(M) = 1e6

인트 계산

• 접두사와 접미사가 같은 최대 길이 : 1e6

코드

#include <iostream>
#include <string>
#include <vector>
 
 
using namespace std;
 
 
vector<int> fail(string& s) {
    vector<int> f(s.size());
    
    int j=0;
    for(int i=1; i<s.size(); i++) {
        while(j>0 && s[i] != s[j]) j = f[j-1];
        if(s[i] == s[j]) f[i] = ++j;
    }
    
    return f;
    
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    
    while(1) {
        string s; cin >> s;
        if(s == ".") break;
        
        int maxv = 0;
        vector<int> f = fail(s);
        
        
        if(f[s.size()-1] % (s.size() - f[s.size()-1])) cout << 1 << '\n';
        else cout <<s.size()/(s.size()-f[s.size()-1]) << '\n';
    }
    return 0;
}
 

문제유형

• KMP - 문자열 제곱
  • 문자열 안에서 작은 문자열이 최대 몇개 반복되는지 확인
  • 문자열 길이 - fail 함수의 마지막 인덱스 = 반복되는 문자 길이
  • 단, 접두사와 접미사가 중간에 겹치는 경우 확인(팰린드롬)