【算法问题】字符串匹配拆分

Question

工作中遇到一个问题，拿来给朋友们做做脑筋体操，欢迎提出有创意的算法。源代码可以，能用文字说明算法思路更好 :)问题是这样的：有一个字符串作为样板，用它来对目标字符串进行匹配拆分。比如样板是 "86041049799715"，目标字符串是 "86041049839715"，那么，希望得到的结果是：
array( "86041049"=>"match", "83"=>"not match", "9715"=>"match" );
或者换一种描述方法：
$tmpl   = "86041049799715";
$target = "86041049839715";
$result = strMatch( $tmpl, $target );
// 希望 $result 为 array( "86041049"=>"match", "83"=>"not match", "9715"=>"match" )function strMatch( $tmpl, $target )
{
    // 这里是需要实现的算法
}
————————————————————————————————
基于CSDN论坛提供的插件扩展功能，自己做了个签名档工具，分享给大家，欢迎技术交流 :)[/size]

Answer 1

$tmpl   = "86041049799715";
$target = "86041049839715";
$result = strMatch( $tmpl, $target );
// 希望 $result 为 array( "86041049"=>"match", "83"=>"not match", "9715"=>"match" )print_r($result);function strMatch( $tmpl, $target ) {
  $k = 1;
  $t = '';
  for($i=0; $i<strlen($tmpl); $i++) {
    if(($tmpl{$i} == $target{$i} && $k) || ($tmpl{$i} != $target{$i} && !$k)) {
      $t .= $k ? $tmpl{$i} : $target{$i};
    }else {
      $r[$t] = ($k ? '' : 'no') .'match';
      $k ^= 1;
      $t = $k ? $tmpl{$i} : $target{$i};
    }
  }
  $r[$t] = ($k ? '' : 'no') .'match';
  return $r;
}Array
(
    [86041049] => match
    [83] => nomatch
    [9715] => match
)

Answer 2

前提定为两字段等长：
开始：
样板串：$str0
目标串：$str1
结果集：$arr('match0'=>,'not match0'=>,....);
计数器：$match,$notmatch，初始均为0
标识符：$flag，初始为1算法：在等字长的前提下，将$str1与$str0按字符匹配，如等价则计入$arr["match".($flag&1)?$match:++$match],且令$flag=1,否则计入$arr["not match".!($flag&0)?$notmatch:++$notmatch],且令flag=0，匹配结束后，结果集数组键值互换，且key值去最后一位数字代码不写了，抛砖引玉，效率不太如意，欢迎大虾们拿仙玉砸咱~

Answer 3

这种允许吗？
$tmpl   = "86041049799715";
$target = "83860410499715";
$result = strMatch( $tmpl, $target );
$result 为 array( "86041049"=>"match", "83"=>"not match", "9715"=>"match" )

Answer 4

拆分的依据就是：连续的相同的串拆成单独的一个串，并标记为 "match"；连续的不相同的串拆成单独的一个串，并标记为 "not match"。
————————————————————————————————
基于CSDN论坛提供的插件扩展功能，自己做了个签名档工具，分享给大家，欢迎技术交流 :)[/size]

Answer 5

你的代码我看懂了。就是顺序扫描，用一个开关在“相同”和“不相同”之间反复切换，发生切换时就把前面刚刚攒到的串输出，并重新开始攒新的串。这个算法直接从需求逻辑入手，简单直接，容易看懂。不错 :)
————————————————————————————————
基于CSDN论坛提供的插件扩展功能，自己做了个签名档工具，分享给大家，欢迎技术交流 :)[/size]

Answer 6

有bug的，假如原串是11，样串是12，第一个1是'1'=>'match'，到了第二个1，应该是'1'=>'nomatch',那这个时候结果集里只会有一个值，'1'=>'nomatch'

Answer 7

hehe, 的确有这个问题，看来原问题对结果形式的定义有缺陷。那就改成下面的样子吧，倒是对“算法”本身没有太大的影响 :)
array
  0 => 
    array
      'text' => string '86041049' (length=8)
      'match' => boolean true
  1 => 
    array
      'text' => string '83' (length=2)
      'match' => boolean false
  2 => 
    array
      'text' => string '9715' (length=4)
      'match' => boolean true
多谢 zhang6464 细心纠正！

Answer 8

haha，还是你想得周到  ^_^不过，从我的实际应用场景看，不需要那么复杂，都是从第一个字符开始比较，而且，所有字符串（一个样板字符串、多个目标字符串）的长度都是一致的。

Answer 9

我的实现代码在这里。算法思路跟 2 楼的基本一样，因为使用了几个 PHP 的数组函数，估计效率会稍微差一点，不过可读性也好一点（我自己认为）：
class Splitter
{
    private function equal( $cTarget, $cTmpl )
    {
        return $cTarget == $cTmpl;
    }    private function merge( $char, $idx )
    {
        // 临时字符串
        $this->segment = $this->segment . $char;        // 如果当前字符的“标志”跟下一个字符的“标志”不一样，则把当前的临时字符串做输出
        if ( $idx == count($this->flags)-1 || $this->flags[$idx] != $this->flags[$idx+1] ) {
            //$this->result[$this->segment] = $this->flags[$idx] ? 'match' : 'not match';
            $this->result[] = array(
                                'text'   => $this->segment,
                                'match' => $this->flags[$idx]
                            );
            $this->segment = '';
        }
    }    public function split( $tmpl, $target )
    {
        // 把“目标字符串”拆解成“目标字符数组”
        $chars = str_split($target);        // 把“样板字符串”也拆解成字符数组，并逐个与“目标字符数组”相比较，得到“标志数组”
        $this->flags = array_map( array($this, 'equal'), $chars, str_split($tmpl) );        // 用于保存最终的拆分结果
        $this->result = array();        // 拆分过程中的临时字符串
        $this->segment = '';        // 遍历“目标字符数组”，对相邻的“标志相同”的字符进行合并
        array_walk( $chars, array($this, 'merge') );        return $this->result;
    }
}function strMatch( $tmpl, $target )
{
    $splitter = new Splitter;
    return $splitter->split( $tmpl, $target );
}$tmpl   = "86041049799715";
$target = "86041049839715";
$result = strMatch( $tmpl, $target );
var_dump($result);
————————————————————————————————
基于CSDN论坛提供的插件扩展功能，自己做了个签名档工具，分享给大家，欢迎技术交流 :)[/size]

Answer 10

感谢各位的参与，结贴了 :)
————————————————————————————————
基于CSDN论坛提供的插件扩展功能，自己做了个签名档工具，分享给大家，欢迎技术交流 :)[/size]