Advertisement
09-05-2020
Fast Algorithms for the Shortest Unique Palindromic Substring Problem on Run-Length Encoded Strings
Published in: Theory of Computing Systems | Issue 7/2020
Log inActivate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Abstract
For a string S, a palindromic substring S[i..j] is said to be a shortest unique palindromic substring (SUPS) for an interval [s,t] in S, if S[i..j] occurs exactly once in S, the interval [i,j] contains [s,t], and every palindromic substring containing [s,t] which is shorter than S[i..j] occurs at least twice in S. In this paper, we study the problem of answering SUPS queries on run-length encoded strings. We show how to preprocess a given run-length encoded string RLES of size m in O(m) space and \(O(m \log \sigma _{\mathit {RLE}_{S}} + m \sqrt {\log m / \log \log m})\) time so that all SUPSs for any subsequent query interval can be answered in \(O(\sqrt {\log m / \log \log m} + \alpha )\) time, where α is the number of outputs, and \(\sigma _{\mathit {RLE}_{S}}\) is the number of distinct runs of RLES. Additionaly, we consider a variant of the SUPS problem where a query interval is also given in a run-length encoded form. For this variant of the problem, we present two alternative algorithms with faster queries. The first one answers queries in \(O(\sqrt {\log \log m /\log \log \log m} + \alpha )\) time and can be built in \(O(m \log \sigma _{\mathit {RLE}_{S}} + m \sqrt {\log m / \log \log m})\) time, and the second one answers queries in \(O(\log \log m + \alpha )\) time and can be built in \(O(m \log \sigma _{\mathit {RLE}_{S}})\) time. Both of these data structures require O(m) space.