0

我在 PHP 中有一个 KMP 代码，它可以在单词到文本之间进行字符串匹配。我想知道是否可以使用 KMP 算法进行文本到文本之间的字符串匹配。有没有可能？以及如何使用它来查找 2 个文本之间的字符串匹配。

这是KMP算法的核心：

<?php
    class KMP{
      function KMPSearch($p,$t){
        $result = array();
        $pattern = str_split($p); 
        $text    = str_split($t);
        $prefix = $this->preKMP($pattern);
    // print_r($prefix);

     // KMP String Matching
     $i = $j = 0;
        $num=0;
        while($j<count($text)){
          while($i>-1 && $pattern[$i]!=$text[$j]){
         // if it doesn't match, then uses then look at the prefix table
            $i = $prefix[$i];
          }
          $i++;
          $j++;
      if($i>=count($pattern)){
         // if its match, find the matches string potition
      // Then use prefix table to swipe to the right.
            $result[$num++]=$j-count($pattern);
            $i = $prefix[$i];
          }
        }
     return $result;
      }

      // Making Prefix table with preKMP function
      function preKMP($pattern){
        $i = 0;
        $j = $prefix[0] = -1;
        while($i<count($pattern)){
          while($j>-1 && $pattern[$i]!=$pattern[$j]){
            $j = $prefix[$j];
          }
          $i++;
          $j++;
          if(isset($pattern[$i])==isset($pattern[$j])){
            $prefix[$i]=$prefix[$j];
          }else{
            $prefix[$i]=$j;
          }
        }
        return $prefix;
      }
    }
    ?>

如果我想在文本上查找单词，我将这个类调用到我的 index.php 中。

这是我希望我的代码执行的步骤：（1）。我输入文本 1 (2)。我输入文本 2 (3)。我希望文本 1 成为模式（文本 1 中的每个单词都被视为模式）（4）。我希望我的代码可以在文本 2 (5) 中的文本 1 上找到每个模式。最后，我的代码可以告诉我相似度的百分比。

希望大家能帮助我或者教教我。我一直在到处寻找答案，但还没有找到。至少你可以教我。

4

1 回答 1

-1

如果您只需要查找两个文本中都存在的所有单词，则不需要任何字符串搜索算法来执行此操作。您可以将第一个文本中的所有单词添加到哈希表中，遍历第二个文本并将哈希表中的单词添加到输出列表中。

如果您想在最坏的情况下获得线性时间复杂度，您可以使用 trie 代替哈希表，但我会从哈希表开始，因为它易于使用并且可能足以满足实际用途。

于 2017-05-20T10:49:56.897 回答