Отправляет email-рассылки с помощью сервиса Sendsay

Олимпиадные задачи и алгоритмы на C++

Рассылка закрыта

При закрытии подписчики были переданы в рассылку "Обзор инструментов SEO-оптимизатора и методов продвижения" на которую и рекомендуем вам подписаться.

Вы можете найти рассылки сходной тематики в Каталоге рассылок.

  Апрель 2004   →
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
Автор
Виктор Журавлев

Статистика

1.725 подписчиков
-1 за неделю
←   Все выпуски   →

Олимпиадные задачи и алгоритмы на C++ Олимпиадные задачи и алгоритмы на C++


Информационный Канал Subscribe.Ru

Олимпиадные задачи и алгоритмы на C++

    Здравствуйте, уважаемые подписчики.

     В этом выпуске: описание алгоритма КМП-поиска и две новые задачи.

Поиск подстроки в строке. Алгоритм Кнута-Морриса-Пратта.

    Постановка задачи. Даны две строки A[1..n] и B[1..m]. Требуется определить, является ли строка B подстрокой строки A. Если является, то найти все позиции ее вхождения в A. Например, для A="abcadababcabca" и B="abca" имеем следующие позиции вхождения B в A: 1 (abcadababcabca), 8 (abcadababcabca), 11 (abcadababcabca).

    Решение. Наиболее простой алгоритм заключается в переборе всех (n-m+1) смещений и проверке за O(m) каждого из них. В итоге - сложность в худшем случае получается O((n-m+1)*m), или проще O(n*m). Код, реализующий данный алгоритм, выглядит так (индексация массивов с 1): 

for (i = 1; i <= n-m+1; i++)
{
  j = 0;
  while (j < m && A[i+j] == B[j+1]) j++;
  if (j == m) printf("%d\n", i);
}
    Данный алгоритм пригоден лишь при маленьких значениях n и m. Существуют более эффективные алгоритмы поиска подстрок, например: алгоритм Рабина-Карпа, алгоритм Кнута-Морриса-Пратта, алгоритм Бойера-Мура. Алгоритм Рабина-Карпа основан на использовании специальной хэш-функции. Она позволяет проверять не все возможные смещения, а лишь часть из них. В худшем случае сложность алгоритма составляет O(n*m). Алгоритм Бойера-Мура также в худшем случае имеет сложность O(n*m). Алгоритм Кнута-Морриса-Пратта (далее, КМП) работается со сложностью O(n+m) на любом тесте. Рассмотрим его более подробно.

    Введем ряд вспомогательных определений. Назовем префиксом длины i строки s ее подстроку с 1 по i-й символ. В частности, префикс длины len(s) - это сама строка s, префикс длины 0 - пустая строка. Аналогично, суффиксом длины i будем называть подстроку из последних i символов строки. Префикс длины i будем обозначать pref(s,i), а суффикс - suf(s,i).

    Введем функцию f, определенную на множестве непустых строк. f(s) = max(i: 0 <= i < len(s), pref(s,i) = suf(s,i)). Если сформулировать словами, то f(s) - это максимальная длина префикса строки s, такого что суффикс соответствующей длины совпадает с этим префиксом. Отметим, что рассматриваются префиксы длины строго меньше длины строки.

    Пусть дана непустая строка s. Поставим задачу поиска f(pref(s,i)) для всех i от 1 до len(s). Сразу отметим, что f(pref(s,1)) = 0, как для строки длины 1. Пусть мы нашли f(pref(s,j)) для всех j от 1 до i-1. Теперь нам нужно найти f(pref(s,i)). Рассмотрим последовательность чисел x1 = f(pref(s,i-1)), x2 = f(pref(s,x1)), x3 = f(pref(s,x2)), ..., xk = 0. Это строго убывающая последовательность чисел, заканчивающаяся нулем. Обозначим t = pref(s,i-1). На самом деле, элементы последовательности xi образуют множество {p: 0 <= p < len(t), pref(t,p) = suf(t,p)}. Пусть k = f(pref(s,i)), k > 0. тогда pref(t,k-1) = suf(t,k-1). Таким образом, мы получаем, что искомое k лежит среди чисел x1+1, x2+1, x3+1, ..., или же k = 0.

    Напишем код, который по заданной строке B длины m заполняет массив C размера m, так что C[i] = f(pref(B,i)). 


C[1] = 0;
k = 0;
for (i = 2; i <= m; i++)
{
  while (k > 0 && B[k+1] != B[i]) k = C[k];
  if (B[k+1] == B[i]) k++;
  C[i] = k;
}

    Докажем, что сложность полученного алгоритма есть O(m). Переменная k может меняться в пределах от 0 до m-1. На каждой итерации цикла for значение k может увеличиться не более чем на 1. На каждой итерации цикла while значение k уменьшается как минимум на 1. Тогда справедливо следующее неравенство (значение k после i-й итерации for) <= (значение k после (i-1)-й итерации for) - (количество итераций while на i-й итерации for) + 1. Просуммировав это неравенство по всем итерациям цикла for, мы получим, что общее количество итераций цикла while не превосходит 2*m, т.е. равно O(m).

    Как использовать полученный алгоритм для поиска подстроки? Предположим, что мы приписали строку B в начало строки A. Теперь над полученной строкой выполним приведенный выше алгоритм. Строка B будет входить в строку A со смещением i тогда и только тогда, когда C[m+i+m-1] >= m. В результате исходная задача сведена к приведенному выше алгоритму для строки длины m+n.

    Оптимизированный вариант данной идеи используется в следующей алгоритме (КМП-поиск): 


C[1] = 0;
k = 0;
for (i = 2; i <= m; i++)
{
  while (k > 0 && B[k+1] != B[i]) k = C[k];
  if (B[k+1] == B[i]) k++;
  C[i] = k;
}
k = 0;
for (i = 1; i <= n; i++)
{
  while (k > 0 && B[k+1] != A[i]) k = C[k];
  if (B[k+1] == A[i]) k++;
  if (k == m)
  {
    printf("%d\n", i-m+1);
    k = C[k];
  }
}

Задача №3 "Префикс-подстрока" (5 баллов).

Входной файл: input.txt
Выходной файл: output.txt
Ограничение по времени: 1 сек. на тест
Ограничение по памяти: 1 Mb

Условие

     Даны две строки a и b. Требуется найти максимальную длину префикса строки a, который входит как подстрока в строку b. При этом считать, что пустая строка является подстрокой любой строки.

Формат входного файла

     В первой строке входного файла содержится строка a, во второй - строка b. Элементами строк a и b являются произвольные символы ASCII с кодами больше 32. Длина каждой строки от 1 до 30000.

Формат выходного файла

     В выходной файл вывести искомую длину префикса строки a, т.е. целое число от 0 до длины строки a.

Пример входного файла (input.txt)


abcdefghijklmnopqrstuvwxyz
Abcd?aBcd!abCd.abcD!?

Пример выходного файла (output.txt)


3

Пример входного файла (input.txt)


www
http

Пример выходного файла (output.txt)


0

Задача №4 "Палиндром" (8 баллов).

Входной файл: input.txt
Выходной файл: output.txt
Ограничение по времени: 4 сек. на тест
Ограничение по памяти: 1 Mb

Условие

     Назовем строку палиндромом, если она одинаково читается слева направо и справа налево. Примеры палиндромов: "abcba", "55", "q", "xyzzyx". Требуется для заданной строки найти максимальную по длине ее подстроку, являющуюся палиндромом.

Формат входного файла

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

Формат выходного файла

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

Пример входного файла (input.txt)


a123bc9e9c321

Пример выходного файла (output.txt)

5

Пример входного файла (input.txt)


zyxwvutsrqp

Пример выходного файла (output.txt)


1

Оформление, отправка и проверка решений.

    На проверку принимаются решения, написанные на языке C++. Отправляйте свои письма по адресу accepted@narod.ru. Решение должно содержаться в одном файле, вложенном в ваше письмо. Для компиляции, по вашему выбору, будет использоваться программа bcc.exe (Borland C++ 3.1) или cl.exe (Microsoft Visual C++ 6.0). Размер исходного кода не должен превышать 40 Kb. Для каждой задачи отправляйте отдельное письмо. В теле письма укажите следующие данные (пример): 

ник (*): vasya
пароль (*): a193z458w2
фамилия: Иванов
имя: Василий
e-mail: vasya@hotmail.com
номер задачи (*): 1
компилятор (*): cl

    (*) обозначены обязательные для заполнения поля. Ник и пароль вы сами придумаете при отправке своего первого письма. В последующих письмах указывайте те же самые ник и пароль. Я пока не придумал, что делать, если два человека используют один и тот же ник. Так что, старайтесь придумать его так, чтобы никто до вас его еще не придумал :-) Если вы укажите свой e-mail, то с этой проблемой будет легче разобраться. В качестве компилятора укажите bcc или cl. И, главное, не забудьте указать номер задачи!

    При проверке решений, используются стандартные правила acm. Их можно найти, например, на сайте http://acm.baylor.edu. Проверка решений осуществляется на наборе тестов, недоступных участникам. Решение считается принятым, если выдало верный ответ на каждом из тестов. Программа должна считывать данные из указанного в условии входного файла и выдавать результат в указанный в условии выходной файл. Она не должна работать с другими файлами или каталогами. Входной файл нельзя открывать для записи. При доступе к входному и выходному файлу вы должны предполагать, что они находятся в текущей директории. Не используйте консольный ввод или вывод.

    Решения принимаются до субботы следующей недели (1 мая 2004) включительно. В воскресенье вечером будут высланы результаты тестирования и авторские решения.

Ведущий рассылкой: Виктор Журавлев
Вопросы, пожелания, предложения пишите на мой e-mail.

http://subscribe.ru/
E-mail: ask@subscribe.ru 		Отписаться
Убрать рекламу

В избранное