Longest property-preserved common factor: A new string-processing framework
Theoretical Computer Science , Volume 812 p. 244- 251
We introduce a new family of string processing problems. Given two or more strings, we are asked to compute a factor common to all strings that preserves a specific property and has maximal length. We consider three fundamental string properties: square-free factors, periodic factors, and palindromic factors under three different settings, one per property. In the first setting, we are given a string x and we are asked to construct a data structure over x answering the following type of online queries: given a string y, find a longest square-free factor common to x and y. In the second setting, we are given k strings and an integer 1<k′≤k and we are asked to find a longest periodic factor common to at least k′ strings. In the third one, we are given two strings and we are asked to find a longest palindromic factor common to the two strings. We present linear-time solutions for all settings. This is a full and extended version of a paper from SPIRE 2018.
|Theoretical Computer Science|
|Organisation||Centrum Wiskunde & Informatica, Amsterdam (CWI), The Netherlands|
Ayad, L.A.K, Bernardini, G, Grossi, R, Iliopoulos, C.S, Pisanti, N, Pissis, S, & Rosone, G. (2020). Longest property-preserved common factor: A new string-processing framework. Theoretical Computer Science, 812, 244–251. doi:10.1016/j.tcs.2020.02.012