工作中遇到一个问题,拿来给朋友们做做脑筋体操,欢迎提出有创意的算法。源代码可以,能用文字说明算法思路更好 :)问题是这样的:有一个字符串作为样板,用它来对目标字符串进行匹配拆分。比如样板是 "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]

解决方案 »

  1. cvm
  2. $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
    )
      

  3. 前提定为两字段等长:
    开始:
    样板串:$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值去最后一位数字代码不写了,抛砖引玉,效率不太如意,欢迎大虾们拿仙玉砸咱~
      

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

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

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

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

  8. 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 细心纠正!
      

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

  10. 我的实现代码在这里。算法思路跟 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]
      

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