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
{
/**
* 获取最大回文字符串
* @param $str
* @return bool|string
*/
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) { //当前字符和边界碰撞上(条件1)
$lpsArr[$current] = $this->find($str, $current, 1);//暴利算法
if ($maxPd < $lpsArr[$current]) { //更新最大回文的位置
$maxPd = $lpsArr[$current];
$maxCenterPosition = $current;
}
$centerRight = $current + $lpsArr[$current];//更新最大回文右边界
$center = $current;//更新对称中心
} else {//条件2
$symmetry = $center - ($current - $center);//获取镜像位置
$currentRight = $lpsArr[$symmetry] + $current;//获取镜像位置的最大回文右边界
if ($currentRight < $centerRight) {//条件2(1)
$lpsArr[$current] = $lpsArr[$symmetry];
} elseif ($currentRight > $centerRight) {//条件2(2)
$lpsArr[$current] = $centerRight - $current;
} else {//条件2(3)
$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);
}

/**
* 暴力方法
* @param $str
* @param $i
* @param $distance
* @return mixed
*/
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;
}
}