演员的技能用字母A-Z表示,某活动需要演员按顺序完成任务,完成得最多的,可获得奖励。由于演员多才多艺,提前告知任务顺序,很容易完成任务。现在让演员随意表演,最后公布活动任务最长匹配度。如一个演员表演顺序 ABCBDAB,最后活动顺序为BDCABA,那么最大匹配度值为4(匹配值为BCBA或者BDAB)。现在编写程序实现以上功能:
<?php $a = 'ABCBDAB'; $b = 'BDCABA'; $aStrlen = strlen($a); $bStrlen = strlen($b); $maxCount = 0; for ($i=0; $i < $aStrlen; $i++) { $ch = $a[$i]; $aIdx = $i; $bIdx = 0; $count = 0; $next = false; for ($j=$bIdx;$j<$bStrlen; $j++) { if($ch == $b[$j]){ $count++; $bIdx = $j; $next = true; } if($j == $bStrlen-1 && $count != 0 && $aIdx < $aStrlen){ $j = $bIdx; $next = true; } if($next){ if(++$aIdx == $aStrlen){ break; } $next = false; $ch = $a[$aIdx]; } } if($count > $maxCount){ $maxCount = $count; } //假如最大次数大于剩余要比较的字符串,则break if($maxCount >= $aStrlen-$i){ break; } } echo $maxCount;
下一篇:
php利用二叉堆算法来实现 TopK