10298. Степень строки

Обозначим через a * b конкатенацию строк a и b. Например, если a = "abc" и b = "def", то a * b = "abcdef". Если считать конкатенацию строк умножением, то можно определить операцию возведения в степень следующим образом:

a⁰ = “” (пустая строка)

aⁿ⁺¹ = a * aⁿ

По заданной строке s необходимо найти наибольшее значение n, для которого s = aⁿ для некоторой строки a.

Вход. Каждый тест состоит из одной строки s, содержащей печатные символы. Строка s содержит не менее одного и не более миллиона символов. Последний тест содержит точку и не обрабатывается.

Выход. Для каждой входной строки s вывести наибольшее значение n, для которого s = aⁿ для некоторой строки a.

Пример входа

abcd

aaaa

ababab

.

Пример выхода

1
4
3

РЕШЕНИЕ

строки – префикс-функция

Анализ алгоритма

Рассмотрим слово S длиной len, являющееся повторением слова X n раз. То есть S = Xⁿ. Пусть длина слова X равна k, причем оно само не является повторением никакого слова.

Построим префикс-функцию p слова S. Поскольку индексы строки начинаются с нуля, то подстрока S[k ...2k – 1] является копией S[0 ...k – 1] и соответственно p[k] = 1, p[k + 1] = 2, …, p[2k – 1] = k. Третий повтор слова X находится в позициях S[2k ...3k – 1] и при этом p[2k] = k + 1, p[2k + 1] = k + 2, …, p[3k – 1] = 2k. Последняя ячейка префикс-функции p[nk – 1] равна (n – 1)k.

Вычислим разницу: len – p[len – 1] = nk – (n – 1)k = k, что равно длине слова X. Тогда степень n слова S равна len / k. При этом если len не делится на k, то S не является повторением никакого слова и следует положить n = 1.

Реализация алгоритма

В векторе p строим префикс-функцию строки s.

vector<int> p;

char s[1000001];

Функция MaxBorderArray строит префикс-функцию строки s.

vector<int> MaxBorderArray(char *s)

{

int i, j;

vector<int> p(len,0);

p[0] = 0;

for(i = 1; i < len; i++)

{

j = p[i - 1];

while ((j > 0) && (s[i] != s[j])) j = p[j - 1];

if (s[i] == s[j]) p[i] = j + 1; else p[i] = 0;

}

return p;

}

Основная часть программы. Читаем входную строку s, вычисляем ее длину len. Вычисляем в массиве p префикс-функцию.

while (gets(s) && strcmp(s,"."))

{

len = strlen(s);

p = MaxBorderArray(s);

Вычисляем разницу между длиной слова и длиной самого длинного префикса строки s, совпадающей с ее суффиксом.

k = len - p[len-1];

Если длина слова len не делится на полученную разницу res, то входная строка s не является степенью никакой строки. Иначе степень строки s равна len / res.

if (len % k) n = 1; else n = len / k;

printf("%d\n",n);

}