Квантовые и классические алгоритмы для задачи о кратчайшей общей надстроке с множественными вхождениями и запросами

Аннотация

Рассматривается задача 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
Опубликовано на условиях лицензии Creative Commons Attribution 4.0 International (CC BY 4.0)

← К номеру журнала

× Issue cover