Филимоненков Виктор (fiviol) wrote,
Филимоненков Виктор
fiviol

Category:

Программа-цензор

Задача. Алфавит некоторого языка состоит из трех букв. Текстом является любая последовательность букв (без пробелов). Цензор полагает нецензурным любое сочетание из трех подряд идущих разных букв. Встречая такое место в любом месте текста, он вырезает его. Если вновь полученный текст снова содержит нецензурный фрагмент, цензор снова вырезает его и т.д., пока текст не станет полностью цензурным.

Пример. Последовательность текстов, получаемых при редактировании исходного текста (жирным выделены удаляемые на каждом шаге фрагменты):
ААВСВАССААВСАВСВВАСССАВ
ААВСВАССААВСВВАСССАВ
ААВСВАССААВСВВАСС
ААВССААВСВВАСС
ААВССААВСВС
ААВССАВС
ААВСС
АС - полностью цензурный текст!

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

Этой задаче уже лет 7. Программированием я не занимаюсь, поэтому интересные (на мой взгляд) задачи на составление алгоритмов придумываются у меня редко. Напомню предыдущую такую свою задачу, об эффективном ведении интерактивного "торпедного боя": http://fiviol.livejournal.com/70041.html.
Tags: Задачи, Математика
Subscribe

  • И лучше выдумать не мог

    В литературной игре "Пишу Онегина размером" добавлено некоторое количество подсказок и объяснений. Теперь-то правильные ответы хлынут рекой. :)…

  • Кое-что про число 13

    Сегодня 13 лет, как я веду свои "Цветные пустяки". Больше четверти жизни, между прочим. За это время написано 1308 постов, то есть в среднем больше…

  • Ну, за славянскую письменность!

    А моему Журналу 11 лет. Спасибо всем, благодаря кому он по-прежнему Живой! Тут был стандартный баннер от ЖЖ с козлом, мне надоело его видеть в моем…

  • Post a new comment

    Error

    default userpic
    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 23 comments

  • И лучше выдумать не мог

    В литературной игре "Пишу Онегина размером" добавлено некоторое количество подсказок и объяснений. Теперь-то правильные ответы хлынут рекой. :)…

  • Кое-что про число 13

    Сегодня 13 лет, как я веду свои "Цветные пустяки". Больше четверти жизни, между прочим. За это время написано 1308 постов, то есть в среднем больше…

  • Ну, за славянскую письменность!

    А моему Журналу 11 лет. Спасибо всем, благодаря кому он по-прежнему Живой! Тут был стандартный баннер от ЖЖ с козлом, мне надоело его видеть в моем…