<?php
$str = "abababas";
$d1 = [];
$d2 = [];
$l = 0;
$r = -1;
for ($i = 0, $n = strlen($str); $i < $n; $i++) {
$k = ($i > $r ? 1 : min($d1[$l + $r - $i], $r - $i));
while ($i - $k >= 0 && $i + $k < $n && $str[$i - $k] == $str[$i + $k]) {
$k++;
}
$d1[$i] = $k;
if ($i + $k - 1 > $r) {
$l = $i - $k + 1;
$r = $i + $k - 1;
}
}
$l = 0;
$r = -1;
for ($i = 0; $i < $n; $i++) {
$k = ($i > $r ? 0 : min($d2[$l + $r - $i - 1], $r - $i));
while ($i - $k >= 0 && $i + $k + 1 < $n && $str[$i - $k] == $str[$i + $k + 1]) {
$k++;
}
$d2[$i] = $k;
if ($i + $k > $r) {
$l = $i - $k + 1;
$r = $i + $k;
}
}
var_dump($d2);
- Output for 5.5.24 - 5.5.35, 5.6.8 - 5.6.28, 7.0.0 - 7.0.20, 7.1.0 - 7.1.20, 7.2.0 - 7.2.33, 7.3.16 - 7.3.33, 7.4.0 - 7.4.33, 8.0.0 - 8.0.30, 8.1.0 - 8.1.28, 8.2.0 - 8.2.18, 8.3.0 - 8.3.6
- array(8) {
[0]=>
int(0)
[1]=>
int(0)
[2]=>
int(0)
[3]=>
int(0)
[4]=>
int(0)
[5]=>
int(0)
[6]=>
int(0)
[7]=>
int(0)
}
preferences:
180.12 ms | 404 KiB | 183 Q