本文实例讲述了PHP实现求两个字符串最长公共子串的方法。分享给大家供大家参考,具体如下:
前面一篇PHP实现求解最长公共子串问题的方法是基于java改进而来,这里再来看另一种公共子串算法。
代码如下:
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
|
<?php
$a = 'abceee12345309878' ;
$b = 'abceeew2345i09878fsfsfsfabceeewsfsdfsfsabceeew' ;
$c = array ();
$lenht1 = strlen ( $a );
$lenth2 = strlen ( $b );
$startTime = microtime(true);
for ( $i =0; $i < $lenht1 ; $i ++) {
for ( $j =0; $j < $lenth2 ; $j ++) {
$n = ( $i -1>=0 && $j -1>=0)? $c [ $i -1][ $j -1]:0;
$n = ( $a [ $i ] == $b [ $j ]) ? $n +1:0;
$c [ $i ][ $j ] = $n ;
}
}
foreach ( $c as $key => $val ) {
$max = max( $val );
foreach ( $val as $key1 => $val1 ) {
if ( $val1 == $max && $max >0) {
$cdStr [ $max ] = substr ( $b , $key1 - $max +1, $max );
}
}
}
ksort( $cdStr );
$endTime = microtime(true);
echo "Totle time is " . ( $endTime - $startTime ) . " s" . "<br/>" ;
print_r( end ( $cdStr ));
exit ;
?>
|
运行结果:
1
2
|
Totle time is 0.0012800693512 s
abceee
|
希望本文所述对大家PHP程序设计有所帮助。
原文链接:http://blog.csdn.net/yujicun/article/details/51062628