[4354번] 문자열 제곱

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. KMP

2. 실패 함수 이용

이 문제와 [1305번] 광고(http://www.crocus.co.kr/607) 문제는 매우 비슷하다.

이 문제에서 말하고자 하는 것은 문자열 속 어떤 가장 짧은 부분 문자를 이용하면

원래의 문자열을 만들 수 있나이다.

따라서 ababab일 경우 어떤 가장 짧은 부분 문자(ab)를 이용하여 3번을 반복하면 ababab가 되는 것이다.

결국 실패 함수를 구하면 되는데

ababab의 실패 함수는 001234이다.

즉, 전체 길이 - 실패 함수의 마지막 값 :: 6 - 4를 하면 2가 남게되는데 이것이 반복되는 문자를 알려주는 것이다.

최종적으로 6 / (6 - 4)가 답이 되고 3번 반복하면 된다는 것을 알 수 있게 된다. 

소스 코드 : 

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 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59

#include <iostream> #include <cstdio> #include <vector> #include <string>   using namespace std;   char tmp[1000001];   // 실패함수 vector<int> getPi(string p) {     int m = (int)p.size();     int j = 0;       vector<int> pi(m, 0);       for (int i = 1; i< m; i++)     {         while (j > 0 && p[i] != p[j])             j = pi[j - 1];           if (p[i] == p[j])             pi[i] = ++j;     }     return pi; }   int main() {     int n;         string str;          while(1)     {         scanf("%s", tmp);         str = tmp;           // .인 경우 종료         if (str.size() == 1 && str[0] == '.')             return 0;           // 실페 함수중 최대 크기를 가진 값을 ans에 저장         vector<int> ans = getPi(str);         int len = ans.size() - 1;                  // 출력 과정         if (ans[len] == 0)             printf("1\n");                  else             printf("%d\n", str.size() / (str.size() - ans[len]));     }          return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus