Квантовые и классические алгоритмы для задачи о кратчайшей общей надстроке с множественными вхождениями и запросами
Получена: 09.11.2026 Доработана: 10.11.2026 Принята: 12.11.2026
Опубликована: 2026 год, том 30, выпуск 4, С. 286–289
Аннотация
Рассматривается задача SUM-SCS: по словарю из \(n\) строк построить кратчайшую строку, содержащую не менее \(k\) вхождений строк словаря. Изучается версия с множественными запросами (MSUM-SCS): для одного словаря нужно найти длины кратчайших надстрок для \(m\) количеств вхождений \(k_1,\dots ,k_m\). Рассматривается случай, когда строки словаря не являются подстроками друг друга (бесфакторный случай). Предложены квантовый алгоритм со сложностью \(O^*(mn^{1.5}\log k_{\max }+n^{2.5}\log k_{\max }+L)\) и классический со сложностью \(O^*(mn^{2}\log k_{\max }+n^{3}\log k_{\max }+L)\). Здесь \(L\) — суммарная длина строк, \(k_{\max }=\max _{1\leq r\leq m} k_r\), обозначение \(O^*\) скрывает не только константу, но и полилогарифмическую функцию, т.е. полином от \(\log m, \log n,\log \log k_{\max }, \log L\).
Ключевые слова: строки, квантовые алгоритмы, запросная сложность, кратчайшая общая надстрока.
BibTeX
@article{IS-Khadiev-Kapralov-Ilikaev2026,
author = {Хадиев, Камиль Равилевич and Капралов, Руслан Илнарович and Иликаев, Артём Рашитович},
title = {{Квантовые и классические алгоритмы для задачи о кратчайшей общей надстроке с множественными вхождениями и запросами}},
journal = {Интеллектуальные системы. Теория и приложения},
year = {2026},
volume = {30},
number = {4},
pages = {286--289},
}
AMSBIB
\RBibitem{IS-Khadiev-Kapralov-Ilikaev2026}
\by К.\,Р.~Хадиев, Р.\,И.~Капралов, А.\,Р.~Иликаев
\paper Квантовые и классические алгоритмы для задачи о кратчайшей общей надстроке с множественными вхождениями и запросами
\jour Интеллектуальные системы. Теория и приложения
\yr 2026
\vol 30
\issue 4
\pages 286--289
EN