Мы рассматриваем две задачи родственные поиску по шаблону в повреждённом тексте. В обеих задачах наша цель – восстановление оригинальных неповреждённых текста и шаблона оптимальным способом. Задача 1. Для данных повреждённых текста и шаблона восстановить текст и шаблон, максимизировав количество вхождений шаблона в текст. Мы определили суммарное расстояние Хэмминга между текстом длины n и шаблоном длины m как сумму расстояний между всеми парами вида (шаблон, подстрока текста длины m). Задача 2. Для данных повреждённых текста и шаблона восстановить текст и шаблон, минимизировав суммарное расстояние Хэмминга между ними. Мы доказали, что обе задачи NP-трудны и привели эффективные (полиномиальные) алгоритмы решения некоторых важных частных случаев.