论文标题
有效实施Manacher算法
An Efficient Implementation of Manacher's Algorithm
论文作者
论文摘要
Manacher的算法已被证明是最长的全文基因弦问题的最佳选择。但是，该算法的许多现有实现都需要一致需要内存构造的增强字符串的内存构造，其长度是原始字符串的两倍。尽管它发现了广泛的使用，但我们发现这种预处理既不是经济的也不是必要的。我们基于索引映射对Manacher算法进行了更有效的实现，该索引映射使字符串增强过程过时。
Manacher's algorithm has been shown to be optimal to the longest palindromic substring problem. Many of the existing implementations of this algorithm, however, unanimously required in-memory construction of an augmented string that is twice as long as the original string. Although it has found widespread use, we found that this preprocessing is neither economic nor necessary. We present a more efficient implementation of Manacher's algorithm based on index mapping that makes the string augmentation process obsolete.
