Вася и строки

Эта задача не входила в число задач городской олимпиады.  Ее нет на сайте acmp.ru. Задача взята из одной из интернет-олимпиад.

Методически она интересна и относится к важной теме работы со строками. Хотя при ее разборе не рассматриваются эффективные алгоритмы линейной сложности поиска вхождения подстроки в строку, такие как Бойера – Мура, Кнута – Пратта, но и применяемые при решении задачи приемы весьма полезны. Для школьников, интересующихся эффективными алгоритмами работы со строками, можно рекомендовать книгу Дэна Гасфилда «Строки, деревья, последовательности в алгоритмах», которая доступна в интернете.

Содержательную постановку задачи, в которой героем является школьник Вася, не привожу, поскольку в авторском варианте Вася к строкам «притянут за уши». Перехожу сразу к формальной постановке.

Требуется определить, является ли исходная строка периодической. В случае положительного ответа необходимо:

  • Путем циклического сдвига перейти к лексикографически минимальной строке;
  •  Определить период циклической строки.

В тестах длина строки может достигать 10 миллионов символов. Как обычно в олимпиадных задачах накладывается ограничение на время решения задачи, что требует разработки эффективного алгоритма.

Входные данные

Во входном файле INPUT.TXT записана строка длины N (2 ≤ N ≤ 10 000000).

Выходные данные

В выходной файл OUTPUT.TXT необходимо вывести одно из двух сообщений:

  • Строка периодическая;
  • Строка  не периодическая

Если строка периодическая, то вывести строку, задающую период, с учетом циклического сдвига

Примеры

INPUT.TXT                                                      OUTPUT.TXT

aa                                                                            строка периодическая

a

abba                                                                       строка не периодическая

fghacabadpqrfghacabadpqr                        строка периодическая

abadpqrfgha

Идея решения

Две задачи будем решать последовательно:

  1. Определим, является ли исходная строка периодической.
  2. Для периодической строки построим строку, минимальную в лексикографическом порядке  среди всех строк, полученных циклическим сдвигом исходной строки.

Определение периодичности

Будем говорить: строка S периодична с периодом P, если:

  1. S = Pk (строка S состоит из k сцеплений строки P, где k >= 2);
  2. Среди всех строк, удовлетворяющих условию 1, строка P имеет минимальную длину.

Необходимое условие периодичности S с периодом P:

N = k*M,

N – длина строки S, M – длина строки P, k – число повторов.

Назовем префиксом строки S длины k начальную часть строки S, состоящую из k символов. Обозначим через S0 начальный символ префикса, совпадающий с начальным символом строки S. Будем строить множество префиксов возрастающей длины, рассматривая их, как кандидаты в периоды. Каждый кандидат будет проходить проверку, является ли он действительно периодом для S. Когда кандидат проходит проверку, то период найден, — строка является периодической.

Первым кандидатом является префикс длины 1. Он является периодом, если строка представляет многократное вхождение символа S0. Предположим, построен префикс длины i, не прошедший проверку на периодичность. Для построения следующего  кандидата вычисляется индекс вхождения S0 на отрезке [i + 1, n / 2]. Пусть такой индекс найден и равен j. Тогда очередным кандидатом является префикс длины j. Если на отрезке вхождений S0 нет, то множество кандидатов исчерпано, и строка не является периодической. Если кандидат прошел проверку, то строка периодическая и найден ее период. Если проверка не пройдена, то ищется очередной кандидат. Число проверяемых кандидатов не превосходит числа вхождений символа S0 в первую половину строки S (длина периода не может превышать половины от длины строки).

Как выполнить проверку на кандидата на периодичность? Проверять многократные вхождения кандидата в строку крайне неэффективно. Хороший алгоритм предварительно проверяет необходимое условие периодичности. Длина строки S должна быть кратна длине кандидата. Если условие не выполняется, то проверка не пройдена и кандидат отвергается. Если условие выполняется и кратность равна k, то можно построить строку Pk, содержащую k вхождений периода. После чего остается сравнить на равенство две строки — построенную и исходную. Эффективность алгоритма на этом этапе обеспечивается тем, что построение строки Pk можно выполнить за log(k) операций сцепления. В наивном алгоритме выполняется k операций сцепления, так что при больших значениях k число операций на этом этапе можно сократить в тысячи раз (так при k = 220, log(k) = 20, — число операций сокращается более чем в 50 тысяч раз).

Если период найден, то решается вторая задача – среди всех строк, полученных циклическими сдвигами периода, найти лексикографически минимальную строку. Для этого предлагается следующий алгоритм. Вначале отыскивается префикс минимальной длины, такой, что первый символ строки после префикса является минимальным символом строки. Найденный префикс становится суффиксом строки. Затем в цикле строится последовательность префиксов, предшествующих очередному вхождению минимального символа. Если префикс лексикографически больше оставшегося тела строки, то префикс становится суффиксом, и происходит переход к построению следующего префикса. Если префикс меньше, то он расширяется до следующего вхождения. Процесс построения префиксов схож с процессом, применяемым при нахождении периода строки.

На этом описание алгоритма закончим и перейдем к коду на языке C#. Вот код основного метода определяющего периодичность строки и нахождение лексикографически минимального периода:

/// <summary>

/// Определение периодичности строки

/// и ее периода, если строка периодична

/// лексикографически минимальный период

/// </summary>

/// <param name=»str»>исходная строка</param>

/// <param name=»period»>лексикографически минимальный период</param>

/// <returns>true, если строка периодична </returns>

public new bool HasPeriod(string str, out string period)

{

bool result = false;

char ch = str[0];

int n = str.Length, n2 = n/2;

int next = str.IndexOf(ch, 1);

int  m = 0;

period = «»;

string temp = «», res = «»;

while (next <= n2 && !result)

{  //пока есть кандидаты и период еще не найден

if (n % next == 0)

{

//возможна периодичность

period = str.Substring(0, next);

m = n / next;

temp = period;

res = «»;

while (m != 0)

if (m % 2 == 0)

{

m = m / 2;

temp += temp;

}

else

{

m = m — 1;

res += temp;

}

 

if (res == str)

result = true;

else

next = str.IndexOf(ch, next + 1);

}

else next = str.IndexOf(ch, next + 1);

}

if(result)

//лексикографически минимальный период

Make_min_lexi(ref  period);

return result;

}

Определение лексикографически минимального периода выделено в отдельную процедуру:

/// <summary>

/// поиск лексикографически минимального периода

/// используя циклические сдвиги

/// </summary>

/// <param name=»period»>лексикографически минимальный период</param>

void Make_min_lexi(ref string  period)

{

string reform = Prefix_Suffix(period);

char ch = reform[0];

int n = reform.Length;

int next = reform.IndexOf(ch, 1);

string head = «», tail = «», suffix = «»;

while(next > 0)

{

head = reform.Substring(0, next);

tail = reform.Substring(next);

if (head.CompareTo(tail) == 1)

{

reform = tail;

suffix = head + suffix;

next = reform.IndexOf(ch, 1);

if (next < 0)

period = tail + suffix;

}

else

{

next = reform.IndexOf(ch, next + 1);

if (next < 0)

period = head + tail + suffix;

}

}

}

Для нахождения первого префикса и преобразования его в суффикс используется следующий метод:

/// <summary>

/// Находит префикс — начальную подстроку

/// до первого минимального символа

/// и делает префикс суффиксом

/// </summary>

/// <param name=»str»>исходная строка</param>

/// <returns>строка после преобразования (префикс => суффикс)</returns>

public string Prefix_Suffix(string str)

{

string result = str;

int index = Index_min_sym(result);

string prefix = result.Substring(0, index);

result = result.Remove(0, index);

result += prefix;

return result;

}

Функция Index_min_sym находит индекс первого вхождения минимального символа строки:

/// <summary>

/// Поиск минимального символа в str

/// </summary>

/// <param name=»str»>исходная строка</param>

/// <returns>индекс первого вхождения

/// лексикографически минимального символа str</returns>

public int Index_min_sym(string str)

{

int result = 0;

char ch = str[result];

int n = str.Length;

for (int i = 1; i < n; i++)

{

if (str[i] < ch)

{

ch = str[i];

result = i;

}

}

return result;

}

Насколько эффективным получился построенный код. Удовлетворяет ли он требованиям, предъявляемым к программам для получения высокой оценки при прохождении тестов? На моем компьютере на тестах с длиной строки более 10 миллионов время работы программы составляет менее 0, 15 секунды как для периодических, так и не периодических строк.

Построение тестов

Тестирование и программное построение тестов является важной частью работы над программой. Для данной задачи целесообразно было написание методов, позволяющих строить как циклические строки, так и не циклические строки. Тесты должны допускать построение строк разной длины с разной длиной периода, с разной сложностью периода.

Вот метод, позволяющий строить циклическую строку с заданным периодом и заданным числом повторений периода:

/// <summary>

/// Тест построения циклической строки

/// </summary>

/// <param name=»pattern»>P — период строки</param>

/// <param name=»count»>k — число повторений периода</param>

/// <returns>циклическая строка -k повторений P </returns>

public string CreateTestTrue(string pattern, int count)

{

string res = pattern, result = «»;

while (count != 0)

{

if (count % 2 == 0)

{

count = count / 2;

res += res;

}

else

{

count—;

result += res;

}

}

return result;

}

Если в качестве образца задать строку P = “fghacadabfgh”, а число повторений задать равным одному миллиону, то метод вернет строку длиной 12 миллионов, миллион раз повторяя строку P. Заметьте, метод HasPeriod на этом тесте вернет в качестве периода лексикографически минимальный период – строку “abfghfghacad” .

Рассмотрим метод, позволяющий строить тесты со строками, где цикличность нарушается, но в которых содержатся циклические подстроки, так что обнаружение нарушения цикличности достаточно непросто:

/// <summary>

/// Тест построения строки

/// с нарушением цикличности

/// </summary>

/// <param name=»pattern»>период</param>

/// <param name=»count»>число повторений периода</param>

/// <returns>возвращается циклическая строка

/// в середину которой встроена строка из символов *,

/// нарушающая цикличность</returns>

public string CreateTestFalse(string pattern, int count)

{

string head, body, tail, result;

head = CreateTestTrue(pattern, count/2);

tail = CreateTestTrue(pattern, count/2);

body = «»;

for (int i = 0; i < pattern.Length; i++)

body += «*»;

result = head + body + tail;

return result;

}

 

Задача «Счастливый билет»

Вот как представлена эта задача на сайте acmp.ru:

Счастливые билеты

(Время: 1 сек. Память: 16 Мб Сложность: 68%)

Требуется вычислить количество N-значных счастливых билетов. Напомним, что билет называется счастливым, если сумма первой половины его цифр равна сумме другой его половины. Например, билет 564159 счастливый, т.к. 5+6+4=1+5+9.

Входные данные

В единственной строке входного файла INPUT.TXT записано натуральное четное число N (N ≤ 100) – количество цифр в билете.

Выходные данные

В единственную строку выходного файла OUTPUT.TXT нужно вывести одно целое число – количество N-значных счастливых билетов.

Примеры

INPUT.TXT

OUTPUT.TXT

1

4 670

2

6 55252

3

12 39581170420

 

Идея решения

Как всегда начнем с простого решения. Оно может быть неэффективным, но его можно быстро реализовать. Организуем перебор всех N-значных чисел. Если очередное число «счастливое», увеличим счетчик на единицу.

Вот программа, реализующая переборный алгоритм:

/// <summary>

/// Счастливые билеты

/// Переборный алгоритм

/// </summary>

/// <param name=»N»>разрядность билета</param>

/// <returns>число счастливых билетов</returns>

ulong Perebor(int N)

{

ulong M;

ulong NP = Convert.ToUInt64(Math.Pow(10, N));

M = 0;

for (ulong i = 0; i < NP; i++)

{

if (IsHappy(i, N)) M++;

}

return M;

}

Метод IsHappy проверяет билет на «счастье»:

bool IsHappy(ulong x, int N)

{

string sN = x.ToString();

sN = sN.PadLeft(N,’0′);

string s1, s2;

int len = N / 2;

s1 = sN.Substring(N/2, len);

s2 = sN.Substring(0, len);

int sum1 = 0, sum2 = 0;

for (int i = 0; i < len; i++ )

{

sum1 += Convert.ToInt32(s1[i].ToString());

sum2 += Convert.ToInt32(s2[i].ToString());

}

return sum1 == sum2;

}

Для небольших значений N метод работает в приемлемое время. Но уже при N, равном шести, чувствуются задержки, которые становятся практически неприемлемыми с ростом N.

Эффективный алгоритм

Билет счастливый, если сумма цифр левой и правой половины номера совпадает. Зададимся вопросом, каковы могут быть значения суммы? Поскольку разрядность числа N – число четное, то сумма цифр варьируется в интервале [0, 9N/2]. Вместо того, чтобы перебирать все возможные номера, в цикле по всем возможным значениям суммы будем считать сколько номеров дают соответствует данной сумме. Если в одной половинке таких номеров K, то и во второй половинке их столько же, так что общее число счастливых билетов с данной суммой равно K*K.

Идея хорошая, но как посчитать, сколько номеров дают сумму S? От перебора номеров по понятным причинам следует отказаться. Вместо этого следует, зная S, генерировать последовательность номеров, дающих сумму S. Генерацию номеров можно осуществлять последовательно, начиная с максимального номера, двигаясь, пока не будет достигнут минимальный номер.

Для пояснения алгоритма приведу пример. Пусть N = 8, то есть рассматриваются номера из восьми цифр. Половину номера составляют четыре цифры и максимально возможная сумма S равна 36. Рассмотрим одно из возможных значений суммы, например S = 15. Максимальный номер из четырех цифр, дающий эту сумму равен 9600, минимальный – 0069. Номер, следующий по порядку за номером 9600 и дающий ту же сумму, равен 9510. Таким образом задача сводится к задаче вычисления следующего по порядку номера с заданной суммой, если известно предыдущее значение номера. Интуитивный алгоритм понятен, его формализация требует аккуратных рассуждений. Приводить их не буду, понять их можно будет, анализируя программу, реализующую данный алгоритм.

Еще одно важное усовершенствование алгоритма состоит в учете того факта, что число номеров, дающих сумму M, равно числу номеров, дающих сумму Smax – M. Так номеров из четырех цифр с суммой 0000 ровно столько же как и номеров 9999 ( для этих сумм существует ровно один номер. Этот факт позволяет практически вдвое сократить объем вычислений.

Основные идеи пояснены, остальное можно понять, анализируя программу:

/// <summary>

/// Счастливые билеты

/// </summary>

/// <param name=»N»>разрядность числа</param>

/// <returns>число счастливых билетов</returns>

ulong Parser(int N)

{

ulong M = 0, K = 0;

int len = N / 2;

int[] digits = new int[len];    //цифры числа

int[] digits_final = new int[len];

int Smax = (9 * len + 1)/2;

for (int S = 0; S < Smax ; S++ )

{//цикл по возможным значениям суммы чисел

//генерация первого числа

FirstNumber(S, digits, digits_final);

K = 1;

//цикл получения следующих чисел с той же суммой

while (ExistNextNumber(digits, digits_final))

K++;

M += K * K;

}

//Четно или нечетно N/2

if(len % 2 != 0)

return  2 * M;

else

{

FirstNumber(Smax , digits, digits_final);

K = 1;

//цикл получения следующих чисел с той же суммой

while (ExistNextNumber(digits, digits_final))

K++;

return 2 * M + K * K;

}

}

Генерация первого и последнего номера  выполняется в методе FirstNumber:

/// <summary>

/// Генерация первого (максимального) номера

/// и последнего (минимального) номера,

/// цифры которых дают сумму S

/// </summary>

/// <param name=»S»>заданная сумма</param>

/// <param name=»digits»>цифры первого номера</param>

/// <param name=»digits_final»>цифры последнего номера</param>

void FirstNumber (int S, int[] digits, int[] digits_final)

{

//формируем первое число и последнее число с суммой цифр S

int d = S;

int len = digits.Length;

for (int i = 0; i < len; i++)

{

if (d > 9)

{

digits[i] = 9;

d = d — 9;

}

else

{

digits[i] = d;

d = 0;

}

}

 

for (int i = 0; i < len; i++)

digits_final[i] = digits[len - 1 - i];

}

Основу алгоритма составляет метод ExistNextNumber, позволяющий генерировать следующее число с заданной суммой:

/// <summary>

/// Генерация очередного числа

/// </summary>

/// <param name=»digits»>текущее и следующее число</param>

/// <param name=»digits_final»>последнее число</param>

/// <returns>true, если текущее число не последнее</returns>

bool ExistNextNumber(int[] digits, int[] digits_final)

{

if (final(digits, digits_final)) return false;

int n = digits.Length;

int i = n — 1;

int j = n — 1;

//разбор случаев

//Последнюю цифру можно увеличить,

//предпоследнюю уменьшить

if (digits[n - 1] != 9 && digits[n - 2] != 0)

{

digits[n - 1]++; digits[n - 2]—;

}

else

//Число заканчивается 9-кой

if (digits[i] == 9)

{

int n9 = 1;

while (digits[i - 1] == 9) { i—; n9++; }

int item = digits[i - 1] + 1;

i—;

int i0 = 0;

while (digits[i - 1] == 0) { i—; i0++; }

digits[i - 1]—;

for (int k = 0; k < n9; k++ )

digits[i + k] = 9;

i += n9;

digits[i] = item;

i++;

while (i < n)

{ digits[i] = 0; i++; }

}

else

//Число заканчивается нулем

{

while (digits[i - 2] == 0) i—;

{

digits[i - 2]—;

digits[i - 1] = digi/tdppts[n - 1] + 1;

digits[n - 1] = 0;

}

}

return true;

}

Простой метод final завершает программу определения количества «счастья»:

/// <summary>

/// Проверка завершения

/// </summary>

/// <param name=»d»>первое число</param>

/// <param name=»f»>последнее число</param>

/// <returns>true, если числа совпадают</returns>

bool final(int[] d, int[] f)

{

int n = d.Length;

bool res = true;

int i = 0;

while (i < n && d[i] == f[i]) i++;

res = (i == n);

return res;

}

 

.

 

 

 

 

gt;