爱悠闲 > 分类 >

算法 第1页

Manacher算法: O(n)时间求字符串的最长回文子串
回文串包括奇数长的和偶数长的,一般求的时候都要分情况讨论,这个算法做了个简单的处理把奇偶情况统一了。算法的基本思路是这样的,把原串每个字符中间用一个串中没出现过的字符分隔开来(统一奇偶),用一个数组p[ i ]记录以 str[ i ] 为中间字符的回文串向右能匹配的长度。先看个例子 原串:w a a b w s w f d 新串: # w # a # a # b # w # s # w # f #