1 Тема от aza_inf

  • aza_inf
  • Участник
  • Неактивен
  • Зарегистрирован: 2009-06-30
  • Сообщений: 78

Тема: Текстовый редактор

При поиске строки в тексте текстовый редактор выделяет все найденные вхождения  строки в
тексте. Например, для текста "hello world" при поиске строки "o" будут выделены обе буквы "o".
Следует  заметить,   что   вхождения   строки  в   текст  могут  перекрываться   между   собой.   Для
заданного текста и строки требуется посчитать количество выделенных букв.

Формат входных данных
Первая строка входного файла содержит текст, длиной не меньше 1 и не больше 500000 симво-
лов. Вторая строка содержит строку поиска длиной не меньше 1 и не больше 500000 символов.
Текст и строка поиска состоят из строчных букв английского алфавита и пробелов.

Формат выходных данных
Выходной файл должен содержать одно целое неотрицательное число - количество выделенных
букв.

например:
input.txt
ababa
aba
output.txt
5

2 Ответ от brainail Отредактировано brainail (2010-03-14 22:17:29)

  • brainail
  • Участник
  • Неактивен
  • Зарегистрирован: 2009-06-22
  • Сообщений: 165

Re: Текстовый редактор

Пишем обычный KMP, или Z-algorithm. Оба алгоритма описаны на сайте, или любой другой алгоритм поиска вхождений строки. Потом легко, в процессе поиска, можно сразу считать только не перекрывающиеся части и прибавлять к ответу.

Сложность : O(N), или O(N*log(N)) смотря как писать и чем.

3 Ответ от coder.ua

  • coder.ua
  • Участник
  • Неактивен
  • Зарегистрирован: 2010-03-06
  • Сообщений: 78

Re: Текстовый редактор

Я не очень силён в строках,но для таких ограничений можно взять массив логического типа где b(i)=true,если символ s(i)-выделен.И по окончанию поиска подстроки считаем количество b(i)=true для всех i(1..length(s)).Ну а сам поиск лучше реализовать через КМП.