Palindrome pattern matching

详细信息    查看全文

• 作者：Tomohiro I ; ^{tomohiro.i@inf.kyushu-u.ac.jp} ; Shunsuke Inenaga ^{inenaga@inf.kyushu-u.ac.jp} ; Masayuki Takeda ^{takeda@inf.kyushu-u.ac.jp}
• 关键词：Palindromes ; Pattern matching ; Linear time algorithms ; Border arrays ; Suffix trees
• 刊名：Theoretical Computer Science
• 出版年：2013
• 出版时间：29 April, 2013
• 年：2013
• 卷：483
• 期：Complete
• 页码：162-170
• 全文大小：363 K

文摘

A palindrome is a string that reads the same forward and backward. For a string , let be the set of all maximal palindromes of , where each maximal palindrome in is encoded by a pair of its center and its radius . Given a text of length and a pattern of length , the palindrome pattern matching problem is to compute all positions of such that . We present linear-time algorithms to solve this problem.