11875번: MULTIGRAM

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


$O(dl)$
// d: 약수 개수
* 약수 개수의 상한:
http://math.stackexchange.com/questions/63687/bound-for-divisor-function

문자열 길이 l의 약수 d(d<l)에 대해
문자열을 d개씩 묶어 알파벳이 같은 개수씩 있는지 확인한다.
조건을 만족하는 가장 작은 d가 답이며 그러한 d가 없다면 불가능.

#include<cstdio>
#include<cstring>
int l;
char s[100001];
int main() {
    scanf("%s", s);
    l = strlen(s);
    for (int i = 1; i<l; i++) {
        if (l%i) continue;
        int c1[128] = { 0, };
        for (int j = 0; j<i; j++) c1[s[j]]++;
        for (int j = i; j<l; j += i) {
            int c2[128] = { 0, };
            for (int k = j; k<j + i; k++) if (++c2[s[k]]>c1[s[k]]) goto bb;
        }
        s[i] = 0;
        puts(s);
        return 0;
    bb:;
    }
    puts("-1");
    return 0;
}