백준[4354] 문자열 제곱

문제 설명

풀이

해쉬를 이용하여 풀이할 수 있습니다.

abababab라는 문자열이 있다면 이것을 ab/ab/ab/ab -> ABCD라고 표현하자.

만약 ABC와 BCD가 같다면 A = B, B = C, C = D라고 할 수 있고, 이때 A의 4 제곱이라고 할 수 있다.

이 ABC와 BCD가 같은지 확인할 때 해쉬를 이용한다.

이 해쉬코드 값을 빠르게 구하기 위해서는 미리 부분 해쉬 값을 구해 놓는다. phash[i]는 0~i까지의 해쉬값이다. 

또한 부분 문자열이 될 수 있는 길이의 후보는 전체 문자열의 길이의 약수들이기 때문에 약수들만 확인한다.

코드

#include <cstdio>
#include <cstring>
#include <string>

using namespace std;
using ll = long long;

const ll MOD = 1e9 + 33;
ll phash[1000006], pow[1000006];
string s;

inline ll mod(ll n) {
    if (n >= 0) return n % MOD;
    return n % MOD + MOD;
}

ll calHash(int l, int r) {
    if (l == 0) return phash[r];
    if (l == r) return s[l];
    return mod(phash[r] - ((phash[l - 1] * pow[r - l + 1]) % MOD + MOD) % MOD);
}

int main() {
    pow[0] = 1;
    for (int i = 1; i < 1000006; i++) pow[i] = mod(pow[i - 1] * 31);
    while (1) {
        char tmp[1000006]; scanf("%s", tmp);
        s = tmp;
        if (s == ".") return 0;

        phash[0] = s[0];
        for (int i = 1; i < s.length(); i++)
            phash[i] = mod(phash[i - 1] * 31 % MOD + s[i]);

        for (int i = 1; i <= s.length(); i++) {
            bool flag = false;
            if (s.length() % i == 0) { // 약수인 경우
                if (calHash(0, s.length() - i - 1) == calHash(i, s.length() - 1)) flag = true;
                if (i == s.length()) flag = true;
            }
            if (flag) {
                printf("%lu\n", s.length() / i);
                break;
            }
        }
    }    
}