# zbMATH — the first resource for mathematics

Searching for gapped palindromes. (English) Zbl 1187.68367
Summary: We study the problem of finding, in a given word, all maximal gapped palindromes verifying two types of constraints, that we call long-armed and length-constrained palindromes. For each of the two classes, we propose an algorithm that runs in time $$O(n+S)$$ for a constant-size alphabet, where $$S$$ is the number of output palindromes. Both algorithms can be extended to compute biological gapped palindromes within the same time bound.

##### MSC:
 68R15 Combinatorics on words
Full Text:
##### References:
 [1] Droubay, X., Palindromes in the Fibonacci word, Information processing letters, 55, 4, 217-221, (1995) · Zbl 1004.68537 [2] Droubay, X.; Pirillo, G., Palindromes and Sturmian words, Theoretical computer science, 223, 73-85, (1999) · Zbl 0930.68116 [3] De Luca, A.; De Luca, A., Palindromes in Sturmian words, (), 199-208 · Zbl 1132.68519 [4] Allouche, J.-P.; Baake, M.; Cassaigne, J.; Damanik, D., Palindrome complexity, Theoretical computer science, 292, 1, 9-31, (2003) · Zbl 1064.68074 [5] Slisenko, A.O., Recognition of palindromes by multihead Turing machines, (), 30-202 [6] Galil, Z., Palindrome recognition in real time by a multitape Turing machine, Journal of computer and system sciences, 16, 2, 140-157, (1978) · Zbl 0386.03020 [7] Slissenko, A., A simplified proof of real-time recognizability of palindromes on Turing machines, Journal of soviet mathematics, Zapiski nauchnykh seminarov LOMI, 68, 1, 123-139, (1977), Russian original · Zbl 0359.02035 [8] Biedl, T.; Buss, J.; Demaine, E.; Demaine, M.; Hajiaghayi, M.; Vinar, T., Palindrome recognition using a multidimensional tape, Theoretical computer science, 302, 1-3, 475-480, (2003) · Zbl 1044.68052 [9] Apostolico, A.; Breslauer, D.; Galil, Z., Parallel detection of all palindromes in a string, (), 497-506 · Zbl 0941.68825 [10] Breslauer, D.; Galil, Z., Finding all periods and initial palindromes of a string in parallel, Algorithmica, 14, 355-366, (1995) · Zbl 0833.68053 [11] Cole, S.N., Real-time computation by $$n$$-dimensional iterative arrays of finite-state machines, IEEE transactions on computers, 18, 349-365, (1969) · Zbl 0172.20804 [12] van de Snepscheut, J.; Swenker, J., On the design of some systolic algorithms, Journal of the ACM, 36, 4, 826-840, (1989) · Zbl 0697.68017 [13] Knuth, D.; Morris, J.; Pratt, V., Fast pattern matching in strings, SIAM journal of computation, 6, 323-350, (1977) · Zbl 0372.68005 [14] Cook, S., Linear time simulation of deterministic two-way pushdown automata, (), 75-80 [15] Manacher, G., A new linear-time on-line algorithm for finding the smallest initial palindrome of a string, Journal of the ACM, 22, 3, 346-351, (1975) · Zbl 0305.68027 [16] Warburton, P.; Giordano, J.; Cheung, F.; Gelfand, Y.; Benson, G., Inverted repeat structure of the human genome: the X-chromosome contains a preponderance of large, highly homologous inverted repeats that contain testes genes, Genome research, 14, 1861-1869, (2004) [17] Lu, L.; Jia, H.; Dröge, P.; Li, J., The human genome-wide distribution of DNA palindromes, Functional and integrative genomics, 7, 3, 221-227, (2007) [18] Gusfield, D., Algorithms on strings, trees, and sequences: computer science and computational biology, (1997), Cambridge University Press · Zbl 0934.68103 [19] Porto, A.H.L.; Barbosa, V.C., Finding approximate palindromes in strings, Pattern recognition, 35, 2581-2591, (2002) · Zbl 1006.68910 [20] Kolpakov, R.; Kucherov, G., Identification of periodic structures in words, (), 430-477, chapter 8 [21] Kolpakov, R.; Kucherov, G., Finding repeats with fixed gap, (), 162-168 [22] Crochemore, M.; Rytter, W., Text algorithms, (1994), Oxford University Press · Zbl 0844.68101 [23] Kolpakov, R.; Kucherov, G., On maximal repetitions in words, Journal of discrete algorithms, 1, 1, 159-186, (2000) [24] M. Crochemore, C. Iliopoulos, M. Kubica, W. Rytter, T. Waleń, Efficient algorithms for two extensions of LPF table: the power of suffix arrays, in: Proc. 36th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM), Lecture Notes in Computer Science, Springer Verlag, 2010 (in press) · Zbl 1274.68670 [25] Kärkkäinen, J.; Sanders, P.; Burkhardt, S., Linear work suffix array construction, Journal of the ACM, 53, 6, 918-936, (2006) · Zbl 1326.68111
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.