Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 
Вернуться
Тема: Можно как то найти Longest Common Subsequence двух строк в линейное время?
1
  1  Неизвестный, 19 июля 2018 г. 22:44:21
      Ну и час как всегда 1 секунда.
  2  Неизвестный, 19 июля 2018 г. 22:43:52
      Я хочу применить это в нахождения наибольшего подпалиндрома(LCS этой стоки с строкой наоборот и есть уже найбольший палиндром,но мне достаточно даже длины),в строке длины не больше 1000,и у меня как есть 10^5 запросов (l,r) на копирование с етой строки сиволов от l до r и находжение подпалиндрома.Я думаю что длину может можко как то по ефективнее найти или я ошибаюсь?
  3  Меньшиков Фёдор Владимирович, 17 июля 2018 г. 18:34:40
      Википедия по этой теме говорит, что в общем случае нет. Однако можно ускорить, если некоторые вещи выполняются. Например, небольшой размер алфавита. Или количество совпадающих пар элементов небольшое.
  4  Неизвестный, 12 июля 2018 г. 12:34:17
      Строки у нас равные по длине.
  5  Неизвестный, 04 июля 2018 г. 19:19:41
      Наибольшую общую подпоследовательность двух строк.
1

Чтобы оставить сообщение необходимо зарегистрироваться и авторизоваться!

Красноярский краевой Дворец пионеров, (c)2006 - 2018, ICQ: 151483