KPM算法实现
改进的模式匹配算法KPM算法
算法思想：在主串S中对串T进行模式匹配时，当第i位失配时，并不是将T向后滑动一位，而是滑动next[i]位，算法关键是需要知道串T中每一位对应的next值。next值为T的每一位的最长前后缀匹配长度，当第i位失配后，就将T向后滑动 i - next[i]位。这样可以保证移动后的T中next[i]前的子串与S串中的相应位置的子串值都相等。
next值得计算算法
算法思想：next中的值是T串中的每一位的最大前后缀匹配长度 + 1。
/*** @name 字符串匹配KPM* @use 使用KPM算法进行字符串匹配* @param sourceStr 主字符串* @param target 需要匹配的字符串* @return int|false 匹配到位置|未匹配到*/public static function strPosKPM($sourceStr, $target){$next = self::countMaxMateLen($target);$j = 0;$index = false;for ($i = 0; $i < strlen($sourceStr); $i++) {if (substr($sourceStr, $i, 1) !== substr($target, $j, 1)) {$j = $next[$j];if ($j != 0) {--$i; }continue;} ++$j;if ($j >= strlen($target)) {$index = $i - strlen($target) + 1;break;}}return $index;}/*** @name 计算最大前后缀匹配长度* @use 计算一个字符串的最大前后缀匹配长度，用于进行KPM算法时使用* @param str 字符串* @return resutl 含有字符串每一位最大前后缀匹配长度的数组*/public static function countMaxMateLen($str) {$length = strlen($str);$result = [0 => -1];$i = 0;$j = -1;while ($i < $length - 1) {if ($j == -1 || substr($str,$i,1) == substr($str,$j,1)) {++$j;++$i;$result[$i] = $j;} else {$j = $result[$j]; }}$result[0] = 0;return $result;}
KPM算法实现
改进的模式匹配算法KPM算法
算法思想：在主串S中对串T进行模式匹配时，当第i位失配时，并不是将T向后滑动一位，而是滑动next[i]位，算法关键是需要知道串T中每一位对应的next值。next值为T的每一位的最长前后缀匹配长度，当第i位失配后，就将T向后滑动 i - next[i]位。这样可以保证移动后的T中next[i]前的子串与S串中的相应位置的子串值都相等。
next值得计算算法
算法思想：next中的值是T串中的每一位的最大前后缀匹配长度 + 1。
/*** @name 字符串匹配KPM* @use 使用KPM算法进行字符串匹配* @param sourceStr 主字符串* @param target 需要匹配的字符串* @return int|false 匹配到位置|未匹配到*/public static function strPosKPM($sourceStr, $target){$next = self::countMaxMateLen($target);$j = 0;$index = false;for ($i = 0; $i < strlen($sourceStr); $i++) {if (substr($sourceStr, $i, 1) !== substr($target, $j, 1)) {$j = $next[$j];if ($j != 0) {--$i; }continue;} ++$j;if ($j >= strlen($target)) {$index = $i - strlen($target) + 1;break;}}return $index;}/*** @name 计算最大前后缀匹配长度* @use 计算一个字符串的最大前后缀匹配长度，用于进行KPM算法时使用* @param str 字符串* @return resutl 含有字符串每一位最大前后缀匹配长度的数组*/public static function countMaxMateLen($str) {$length = strlen($str);$result = [0 => -1];$i = 0;$j = -1;while ($i < $length - 1) {if ($j == -1 || substr($str,$i,1) == substr($str,$j,1)) {++$j;++$i;$result[$i] = $j;} else {$j = $result[$j]; }}$result[0] = 0;return $result;}
发布评论