上次突然想到了一道算法题，题目如下：一个字符串，算出重复且长度最长的子字符串。下面是我写的算法，基本思想是先求出重复的字符串，组成一个数组，在求出该数组每个元素的长度组成一个新的数组，在拆分新的数组，以长度为元素又组成一个新的数组，算出最大值，根据有长度的那个数组每个元素是否有最大值算出该子字符串。
<?php
header ( "content-type:text/html;charset=utf-8" );
/**
* 给一个字符串计算出长度最长的子字符串
*
* @author lxy
*
*/
class maxstr {
private function __construct() {
}
/**
* 筛选出有连续重复的子字符串
*
* @param String $str
* @return Array
*/
private static function strtoarr($str) {
$nwearray = array ();
$oldarray=array();
$newstr = "";
for($i = 0; $i < strlen ( $str ) - 1; $i ++) {
$newstr = "";
for($j = $i + 1; $j < strlen ( $str ); $j ++) {
if ($str [$i] == $str [$j]) {
$newstr .= $str [$j];
} else {
break;
}
}
if (strlen ( $newstr ) > 0) {
$newstr .= $str [$i];
$e = strlen ( $newstr );
$i = $i + $e - 1;
$oldarray [] = $newstr;
}
}
return $oldarray;
}
/**
* 筛选出长度最长的子字符串
*
* @param String $str
* @return Array
*/
private static function maxlenth($str) {
$oldarray = self::strtoarr ( $str);
if(empty($oldarray)){
echo "对不起您没有重复的子字符串";
return false;
}
$lastarray = array ();
$newlenarray = array ();
foreach ( $oldarray as $val ) {
$newarray [] = $val . ‘@‘ . strlen ( $val );
}
foreach ( $newarray as $value ) {
$numarr = explode ( ‘@‘, $value );
$numar [] = $numarr [1];
}
$maxlength = max ( $numar );
foreach ( $newarray as $valu ) {
$varray = explode ( ‘@‘, $valu );
if (array_search ( $maxlength, $varray )) {
$lastarray [] = $varray [0];
}
}
return $lastarray;
}
/**
* 入口文件
*
* @param String $str
* @return Array
*/
public static function main($str) {
$newstr = self::maxlenth ( $str );
return $newstr;
}
}
$str = "aaaeeeeebbbbcd";
$newstr = maxstr::main ( $str );
print_r ( $newstr );