Manacher算法
解决问题:暴利递归查找字符串的算法时间复杂度为O(n^2),在时间复杂度为O(n)解决最长回文子串.
解决思路
1.将字符串分割按拼接#
字符. 例如:“1221”=>“#1#2#2#1#”.目的是为了查找偶回文.
2.-当前字符位置不在回文最右边界内,执行常规查找回文算法(暴利算法)并记录回文最右边界(简称最右边界),回文最右边界的对称中心(简称对称中心)以及回文数组.
-当前字符位置在回文右边界内:
(1)如果当前字符的关于对称中心的镜像位置(简称镜像位置)的回文长度的位置在最右和最左边界内,那么当前字符串回文数组的长度为镜像位置回文数组的长度.
(2)如果当前字符的镜像位置的回文长度的位置在最右和最左边界外,那么当前字符串回文数组的长度为回文最右边界减去当前字符的位置.
(3)如果当前字符的镜像位置的回文长度的位置在最右和最左边界相等,那么当前字符串回文数组的长度需要从最右边界开始继续执行常规查找回文算法.
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73
| class Manacher {
public function getLongestPlalindrome($str) { if (empty($str)) { return false; } $sourceStr = $str; $str = "#" . implode('#', str_split($str)) . "#"; $centerRight = -1; $center = 0; $lpsArr = []; $maxPd = 0; $maxCenterPosition = -1; for ($current = 0; $current < strlen($str); $current++) { if ($current >= $centerRight) { $lpsArr[$current] = $this->find($str, $current, 1); if ($maxPd < $lpsArr[$current]) { $maxPd = $lpsArr[$current]; $maxCenterPosition = $current; } $centerRight = $current + $lpsArr[$current]; $center = $current; } else { $symmetry = $center - ($current - $center); $currentRight = $lpsArr[$symmetry] + $current; if ($currentRight < $centerRight) { $lpsArr[$current] = $lpsArr[$symmetry]; } elseif ($currentRight > $centerRight) { $lpsArr[$current] = $centerRight - $current; } else { $lpsArr[$current] = $this->find($str, $current, $lpsArr[$symmetry]); $center = $current; $centerRight = $current + $lpsArr[$current]; if ($maxPd < $lpsArr[$current]) { $maxPd = $lpsArr[$current]; $maxCenterPosition = $current; } } } } return substr($sourceStr, intdiv($maxCenterPosition - $maxPd + 1, 2), $maxPd - 1); }
public function find($str, $i, $distance) { $left = $i - $distance; $right = $i + $distance; $maxPd = $distance; while ($left >= 0 && $right <= strlen($str) - 1) { if ($str[$left] == $str[$right]) { $maxPd++; } else { break; } $left--; $right++; } return $maxPd; } }
|