Knuth-Morris-Pratt 알고리즘을 사용하여 텍스트와 텍스트의 문자열 일치를 검색 할 수 있습니까?

Question

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의 텍스트 1에있는 모든 패턴을 찾을 수 있기를 바랍니다. (5). 마지막으로, 내 코드는 유사성의 비율을 보여줄 수 있습니다.

여러분 모두 저를 도울 수 있고 가르쳐 주길 바랍니다. 나는 그 대답을 어디에서나 찾아 왔지만 아직 그것을 찾을 수는 없다. 적어도 당신은 저를 가르 칠 수 있습니다.

Answer 1

두 텍스트 모두에있는 단어를 모두 찾으려면 문자열 검색 알고리즘을 사용하지 마십시오. 첫 번째 텍스트의 모든 단어를 해시 테이블에 추가하고 두 번째 텍스트를 반복하고 해시 테이블에있는 단어를 출력 목록에 추가 할 수 있습니다.

최악의 경우 선형 시간 복잡성을 원할 경우 해시 테이블 대신 trie를 사용할 수 있지만 사용하기 쉽고 실용적이기 때문에 해시 테이블을 사용하기 시작합니다. 목적.