Сибирские электронные математические известия
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Общая информация
Последний выпуск
Архив
Импакт-фактор

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS


Сиб. электрон. матем. изв.:
Год:
Том:
Выпуск:
Страница:
Найти




Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация

Сибирские электронные математические известия, 2013, том 10, страницы 538–550 (Mi semr445)  
Дискретная математика и математическая кибернетика

Две задачи о восстановлении поврежденных строк

М. В. Рубинчик, Ю. В. Гамзова

Институт математики и компьютерных наук, Уральский федеральный университет имени первого Президента России Б. Н. Ельцина, 620000, Екатеринбург-83, пр. Ленина, 51
PDF полного текста (537 kB)
Список литературы:
PDF
HTML
Аннотация: We consider two problems related to pattern matching in damaged strings. In both problems, the goal is to recover the original undamaged text and pattern in an optimal way.
Problem 1. For given damaged text and damaged pattern, recover the text and the pattern in a way that maximizes the number of occurrences of the pattern in the text.
We define total Hamming distance between a text of length $n$ and a pattern of length $m$ to be the sum of Hamming distances for all pairs (pattern, factor of length $m$ of the text).
Problem 2. For given damaged text and damaged pattern, recover the text and the pattern in a way that minimizes the total Hamming distance between them.
We prove both problems to be $NP$-hard and provide efficient algorithms to various polynomially solvable subcases of these problems.
Ключевые слова: damaged string, partial strings, pattern matching.
Поступила 25 июля 2013 г., опубликована 3 сентября 2013 г.
Тип публикации: Статья
УДК: 519.16
MSC: 68W32
Образец цитирования: М. В. Рубинчик, Ю. В. Гамзова, “Две задачи о восстановлении поврежденных строк”, Сиб. электрон. матем. изв., 10 (2013), 538–550
Цитирование в формате AMSBIB
\RBibitem{RubGam13}
\by М.~В.~Рубинчик, Ю.~В.~Гамзова
\paper Две задачи о восстановлении поврежденных строк
\jour Сиб. электрон. матем. изв.
\yr 2013
\vol 10
\pages 538--550
\mathnet{http://mi.mathnet.ru/semr445}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/semr445
  • https://www.mathnet.ru/rus/semr/v10/p538
    • Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Статистика просмотров:
    Страница аннотации:276
    PDF полного текста:102
    Список литературы:35
     
      Обратная связь:
    		  Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024