2 Search Results for "Lifshits, Yury"

Document
DOI: 10.4230/LIPIcs.CPM.2025.13
Doubly-Periodic String Comparison

Authors: Nikita Gaevoy, Boris Zolotov, and Alexander Tiskin

Published in: LIPIcs, Volume 331, 36th Annual Symposium on Combinatorial Pattern Matching (CPM 2025)

Abstract
The longest common subsequence (LCS) problem is a fundamental algorithmic problem. Given a pair of strings, the problem asks for the length of the longest string that is a subsequence in both input strings. Among the many relatives of this problem, there is its natural version where one or both of input strings have periodic structure. The case where only one of the input strings is periodic has been considered before; in this work, we develop an efficient algorithm for the more difficult case where both input strings are periodic. The algorithm is based on the existing algebraic framework for the LCS problem, developed by the third author; in particular, we extend this framework to dealing with affine (i.e. doubly-infinite periodic) permutations instead of finite ones. Given input strings that are a k-repeat of a period of length m and an 𝓁-repeat of a period of length n, the resulting algorithm runs in time O(mn+n log n log k), which is a substantial improvement over existing approaches. The algorithm has been implemented by the first author; by running his code, one can process pairs of periodic input strings with lengths far beyond the reach of all known alternative algorithms.
Cite as

Nikita Gaevoy, Boris Zolotov, and Alexander Tiskin. Doubly-Periodic String Comparison. In 36th Annual Symposium on Combinatorial Pattern Matching (CPM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 331, pp. 13:1-13:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{gaevoy_et_al:LIPIcs.CPM.2025.13,
  author =	{Gaevoy, Nikita and Zolotov, Boris and Tiskin, Alexander},
  title =	{{Doubly-Periodic String Comparison}},
  booktitle =	{36th Annual Symposium on Combinatorial Pattern Matching (CPM 2025)},
  pages =	{13:1--13:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-369-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{331},
  editor =	{Bonizzoni, Paola and M\"{a}kinen, Veli},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2025.13},
  URN =		{urn:nbn:de:0030-drops-231079},
  doi =		{10.4230/LIPIcs.CPM.2025.13},
  annote =	{Keywords: String Comparison, periodic Strings, Longest common Subsequence, affine Hecke Monoid, affine sticky Braids}
}
Document
DOI: 10.4230/DagSemProc.06201.7
Solving Classical String Problems an Compressed Texts

Authors: Yury Lifshits

Published in: Dagstuhl Seminar Proceedings, Volume 6201, Combinatorial and Algorithmic Foundations of Pattern and Association Discovery (2006)

Abstract
How to solve string problems, if instead of input string we get only program generating it? Is it possible to solve problems faster than just "generate text + apply classical algorithm"? In this paper we consider strings generated by straight-line programs (SLP). These are programs using only assignment operator. We show new algorithms for equivalence, pattern matching, finding periods and covers, computing fingerprint table on SLP-generated strings. From the other hand, computing the Hamming distance is NP-hard. Main corollary is an $O(n2*m)$ algorithm for pattern matching in LZ-compressed texts.
Cite as

Yury Lifshits. Solving Classical String Problems an Compressed Texts. In Combinatorial and Algorithmic Foundations of Pattern and Association Discovery. Dagstuhl Seminar Proceedings, Volume 6201, pp. 1-10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{lifshits:DagSemProc.06201.7,
  author =	{Lifshits, Yury},
  title =	{{Solving Classical String Problems an Compressed Texts}},
  booktitle =	{Combinatorial and Algorithmic Foundations of Pattern and Association Discovery},
  pages =	{1--10},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6201},
  editor =	{Rudolf Ahlswede and Alberto Apostolico and Vladimir I. Levenshtein},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06201.7},
  URN =		{urn:nbn:de:0030-drops-7984},
  doi =		{10.4230/DagSemProc.06201.7},
  annote =	{Keywords: Pattern matching, Compressed text}
}
  • Refine by Type
  • 2 Document/PDF
  • 1 Document/HTML

  • Refine by Publication Year
  • 1 2025
  • 1 2006

  • Refine by Author
  • 1 Gaevoy, Nikita
  • 1 Lifshits, Yury
  • 1 Tiskin, Alexander
  • 1 Zolotov, Boris

  • Refine by Series/Journal
  • 1 LIPIcs
  • 1 DagSemProc

  • Refine by Classification
  • 1 Mathematics of computing → Combinatorial algorithms
  • 1 Theory of computation → Pattern matching

  • Refine by Keyword
  • 1 Compressed text
  • 1 Longest common Subsequence
  • 1 Pattern matching
  • 1 String Comparison
  • 1 affine Hecke Monoid
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact