Computing longest Lyndon subsequences and longest common Lyndon subsequences

DOI10.1007/S00453-023-01125-ZMaRDI QIDQ6119829zbMATH OpenOpenAlexFDO

Authors Hideo Bannai, Tomohiro I, Tomasz Kociumaka, Dominik Köppl, Simon J. Puglisi

Publication date 25 March 2024

Published in Algorithmica (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1007/s00453-023-01125-z

zbMATH Keywords

dynamic programmingLyndon wordlexicographic ordersubsequence

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

Cites work

• scientific article; zbMATH DE number 1670815 (Why is no real title available?)
• scientific article; zbMATH DE number 2079421 (Why is no real title available?)
• scientific article; zbMATH DE number 7559139 (Why is no real title available?)
• scientific article; zbMATH DE number 6297698 (Why is no real title available?)
• A fast algorithm for computing longest common subsequences
• A hardness result and new algorithm for the longest common palindromic subsequence problem
• Absent subsequences in words
• Algorithms for the Longest Common Subsequence Problem
• Computing a longest common almost-increasing subsequence of two sequences
• Computing a longest common palindromic subsequence
• Computing longest (common) Lyndon subsequences
• Computing longest common square subsequences
• Counting Lyndon factors
• Dynamic LCA Queries on Trees
• Factorizing words over an ordered alphabet
• Faster algorithms for computing longest common increasing subsequences
• Free differential calculus. IV: The quotient groups of the lower central series
• Longest Increasing and Decreasing Subsequences
• Longest common rollercoasters
• Longest common subsequence in sublinear space
• Lowest common ancestors in trees and directed acyclic graphs
• New algorithms on wavelet trees and applications to information retrieval
• On Burnside's Problem
• On generalized Lyndon words
• Permutations, matrices, and generalized Young tableaux
• Rollercoasters: Long Sequences without Short Runs
• String Processing and Information Retrieval
• The String-to-String Correction Problem
• The ``runs theorem
• The longest almost-increasing subsequence
• The longest commonly positioned increasing subsequences problem

Cited in

(2)

• Fast algorithms for window accumulated subsequence matching problem
• Jumbled scattered factors

This page was built for publication: Computing longest Lyndon subsequences and longest common Lyndon subsequences

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6119829)