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 both classes, we propose algorithms that run in time O(n + S), where S is the number of output palindromes. Both algorithms can be extended to compute biological gapped palindromes within the same time bound.
展开▼
