[BOJ 4354, C++] 문자열 제곱

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

4354번: 문자열 제곱

 

이런 상황일 때 실패함수를 사용하는 것이다를 잘 보여준 문제

 

 

 

1. 풀이

---

문제를 잘 읽어보면 S = A^n으로 어떤 문자열 S는 어떤 문자열 A를 n개를 이어 붙인 것이므로 aaaaaab, abaaaaa, aabbaaaa 같은 이런 문자열들은 저 문자열 그대로 A가 되어 S = A^1이 되는 것을 알 수 있습니다.

 

만약 S가 A의 알파벳을 순서대로 계속 붙인 경우라면 실패함수 배열 fail[-1]의 값은 (전체 문자열의 길이) - (A의 길이)가 될 것입니다.

예를 들어서 S = abcabcabc, A = abc인 경우 실패함수의 배열은 0 0 0 1 2 3 4 5 6으로 (전체 문자열의 길이 = 9) - (A의 길이 = 3) = 6이 됩니다.

 

이때 주의할 점은 fail[-1]의 값이 A의 길이와 나누어 떨어지지 않은 경우인데, 이런 케이스는 S = abcabcab 이고, A = abc인 경우입니다. 이런 경우엔 실패함수의 배열은 0 0 0 1 2 3 4 5로 (전체 문자열의 길이 = 8) - (A의 길이 = 3) = 5가 나오지만 5 % 3 = 2이므로 S != A^n로 정답이 아니게 됩니다. 이 케이스만 주의해서 풀면 문제를 해결할 수 있게 됩니다.

---

 

 

 

2. 코드

---

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
 
const int N = 10000001;
 
int n;
int fail[N] = { 0 };
string T;
 
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    while (true) {
        cin >> T;
        if (T == ".") return 0;
 
        int ans = 1;
        memset(fail, 0, sizeof(fail));
 
        for (int i = 1, j = 0; i < T.size(); i++) {
            while (j > 0 && T[i] != T[j]) j = fail[j - 1];
            if (T[i] == T[j]) fail[i] = ++j;
        }
 
        int pattern = T.size() - fail[T.size() - 1];
 
        if (T.size() % pattern) cout << 1 << endl;
        else cout << T.size() / pattern << endl;
    }
}

---