Dynamic LCS maintained under edits in amortized O(log^7 n) time whp, with Omega(log n / log log n) lower bound.
Dynamic Palindrome Detection
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
Lately, there is a growing interest in dynamic string matching problems. Specifically, the dynamic Longest Common Factor problem has been researched and some interesting results has been reached. In this paper we examine another classic string problem in a dynamic setting - finding the longest palindrome substring of a given string. We show that the longest palindrome can be maintained in poly-logarithmic time per symbol edit.
fields
cs.DS 1years
2020 1verdicts
CONDITIONAL 1representative citing papers
citing papers explorer
-
Dynamic Longest Common Substring in Polylogarithmic Time
Dynamic LCS maintained under edits in amortized O(log^7 n) time whp, with Omega(log n / log log n) lower bound.