kmp.php

来自「KMP的PHP描述。有些兄弟可能用得上。具体的请看代码」· PHP 代码 · 共 81 行

<?
/*网上没找到现成的，就根据以前C的写了个PHP的，呵呵，分享。*/
  $a="hello";
  $b="How are you? hello?";

echo kmp($a,$b,0);

function kmp($a,$b,$posB)
{
/*
  从b的第posB个字符开始搜索a，第一次匹配后，返回匹配的起始位置
  a为模式串指针，b为主串指针，posB表示从b的第posB个字符开始匹配。

  a不能为空，否则运行时错误
  0<=posB<=strlen(b)
*/
  $iA=0;
  $iB=$posB;
  $lenA=strlen($a);
  $lenB=strlen($b);

  /* 取得模式串的next函数值 */
  $i=1;
  $j=0;
  $next=array(); //=malloc((lenA+1)*sizeof(unsigned int));

  /* 便于区别个数与序号，不使用 next[0] */
  $next[1]=0;

  while($i<$lenA)
  {
    if($j==0 || $a[$i-1]==$a[$j-1])
    {
      ++$i;
      ++$j;
      if($a[$i-1]!=$a[$j-1])
      {
        $next[$i]=$j;
      }
      else
      {
        $next[$i]=$next[$j];
      }
    }
    else
    {
      $j=$next[$j];
    }
  }

  /* 匹配中 */
  while($iA<=$lenA && $iB<=$lenB)
  {
    if($iA==0 || $a[$iA-1]==$b[$iB-1])
    {
      ++$iA;
      ++$iB;
    }
    else
    {
      $iA=$next[$iA];
    }
  }

  /* 释放next数组 */
  unset($next);

  /* 确定匹配的串的开始位置 */
  if($iA>$lenA)
  {
    return $iB-$lenA;
  }
  else
  {
    return 0;
  }
}
?>