给定一个字符串,求出其最长的重复子串。

近期面试经常出的一道题, 看看大家还有没有更简单的方法:
给定一个字符串,求出其最长的重复子串。

[code lang=”php”]
$str = ‘abcabcabcde’;
$len = strlen($str);
$max_str = ”;
$max_len = 0;
for ($i = 0; $i < $len; $i++) {
for ($j = $len – $i; $j > $i; $j–) {
$sub = substr($str, $i, $j);
$sub_len = strlen($sub);
$left = strpos($str, $sub);
$right = strrpos($str, $sub);
if ($left === false || $right === false) {
continue;
}
if ($left != $right && $sub_len > $max_len && $left + $sub_len <= $right) {
$max_str = $sub;
$max_len = strlen($max_str);
}
}
}
[/code]

发表评论

电子邮件地址不会被公开。 必填项已用*标注