目前使用两种方式处理回文子串
解题思路:通过偏移量来计算,当前字符向外扩张,前提字符串存在奇偶性,需要把字符串处理成奇数,在while循环时务必只循环最大偏移量,否则每次都计算的话,循环次数增加,耗时,当输入字符串长度为1000个a,自己写的用时4ms,马拉车6ms,思路主要也是参考马拉车的,自己在简短处理了下 1,自己处理的方式
$s = "babad";
$len = strlen($s);
if ($len < 1) {
return '';
} elseif ($len <= 2) {
return $s{0} == $s{1} ? $s : $s{0};
}
$t = 1;
$resCenter = 1;
$val = $s{0};
$symbol = '#';
$s_with_symbol = "\$".$symbol;
for ($i = 0; $i < $len; $i ++) {
$sub_s = $s{$i} . $symbol;
$s_with_symbol .= $sub_s;
}
$s_with_symbol_len = strlen($s_with_symbol);
$co = 0;
for ($i = 1; $i < $s_with_symbol_len; $i++) {
$co += 1;
$j = $t;
while($s_with_symbol{$i - $j} == $s_with_symbol{$i + $j}){
$co += 1;
++$j;
if($t < $j){
$t = $j;
$resCenter = $i;
}
}
}
$val = substr($s, ($resCenter - $t)/2, $t);
return $val;
2,马拉车算法方式
$s_len = strlen($s);
if ($s_len < 1) {
return '';
} elseif ($s_len <= 2) {
return $s{0} == $s{1} ? $s : $s{0};
}
$symbol = '#';
$s_with_symbol = "\$" . $symbol;
for ($i = 0; $i < $s_len; $i ++) {
$sub_s = $s{$i} . $symbol;
$s_with_symbol .= $sub_s;
}
$p = [];
$mx = 0;
$id = 0;
$resLen = 0;
$resCenter = 0;
$s_with_symbol_len = strlen($s_with_symbol);
$ir=0;
for ($i = 1; $i < $s_with_symbol_len; $i ++) {
$ir += 1;
$p[$i] = $mx > $i ? min($p[2 * $id - $i], $mx - $i) : 1;
while ($s_with_symbol{$i + $p[$i]} == $s_with_symbol{$i - $p[$i]}) {
++ $p[$i];
$ir += 1;
if ($mx < $p[$i] + $i) {
$mx = $p[$i] + $i;
$id = $i;
}
if ($resLen < $p[$i]) {
$resLen = $p[$i];
$resCenter = $i;
}
}
}
retutn substr($s, ($resCenter - $resLen)/2, $resLen - 1);
|