如何在PHP中的兩個字符串之間找到最大公共子字符串？

Question

是否有一個快速算法找到兩個strings中的最大公共子字符串還是NPCcomplete問題？

在PHP我可以在草堆裏找到一根針：

<?php 

if (strstr("there is a needle in a haystack", "needle")) { 
    echo "found<br>\n"; 
} 
?> 

我想我可以在一個循環中在strings的一個做到這一點，但是這將是非常昂貴的！特別是因爲我的應用程序是搜索電子郵件數據庫並查找垃圾郵件（即由同一個人發送的類似電子郵件）。

有沒有人有任何PHP代碼，他們可以扔出去嗎？

Answer 1

我已經找到a relevant wikipedia article。這不是一個NP完整的問題，它可以在O（mn）時間內使用動態編程算法完成。

在PHP中，我發現similar_text函數非常有用。下面是一個代碼示例，用於檢索一系列文本電子郵件並通過它們進行循環，並找到90％相似的文本電子郵件。 注：像這樣的東西是不可伸縮的：

<?php 
// Gather all messages by a user into two identical associative arrays 
$getMsgsRes = mysql_query(SELECT * FROM email_messages WHERE from = '$someUserID'); 
while($msgInfo = mysql_fetch_assoc($getMsgsRes)) 
{ 
    $msgsInfo1[] = $msgInfo; 
    $msgsInfo2[] = $msgInfo; 
} 

// Loop over msgs and compare each one to every other 
foreach ($msgsInfo1 as $msg1) 
    foreach ($msgsInfo2 as $msg2) 
     similar_text($msg1['msgTxt'],$msg2['msgTxt'],$similarity_pst); 
     if ($similarity_pst > 90) 
      echo "{$msg1['msgID']} is ${similarity_pst}% to {$msg2['msgID']}\n"; 
?> 

Answer 2

特別是因爲我的這個應用是搜索電子郵件的數據庫，尋找垃圾郵件（由同一人發送即類似電子郵件）。

我想你應該看看貝葉斯推理算法，不一定是最長的公共子串。

http://www.devshed.com/c/a/PHP/Implement-Bayesian-inference-using-PHP-Part-1/

Answer 3

的similar_text功能可能是你想要的東西。

這將計算兩個字符串之間的相似度。返回匹配字符的兩個字符串

您可能也想看看levenshtein

Answer 4

請看看Algorithm implementation/Strings/Longest common substring維基教科書上的數量。我沒有測試PHP的實現，但它似乎與維基百科頁面上的一般算法相匹配。

Answer 5

末到本方，但這裏是找到一個字符串數組最大公共子道：

例子：

$array = array(
    'PTT757LP4', 
    'PTT757A', 
    'PCT757B', 
    'PCT757LP4EV' 
); 
echo longest_common_substring($array); // => T757 

功能：

function longest_common_substring($words) { 
    $words = array_map('strtolower', array_map('trim', $words)); 
    $sort_by_strlen = create_function('$a, $b', 'if (strlen($a) == strlen($b)) { return strcmp($a, $b); } return (strlen($a) < strlen($b)) ? -1 : 1;'); 
    usort($words, $sort_by_strlen); 
    // We have to assume that each string has something in common with the first 
    // string (post sort), we just need to figure out what the longest common 
    // string is. If any string DOES NOT have something in common with the first 
    // string, return false. 
    $longest_common_substring = array(); 
    $shortest_string = str_split(array_shift($words)); 

    while (sizeof($shortest_string)) { 
     array_unshift($longest_common_substring, ''); 
     foreach ($shortest_string as $ci => $char) { 
      foreach ($words as $wi => $word) { 
       if (!strstr($word, $longest_common_substring[0] . $char)) { 
        // No match 
        break 2; 
       } // if 
      } // foreach 
      // we found the current char in each word, so add it to the first longest_common_substring element, 
      // then start checking again using the next char as well 
      $longest_common_substring[0].= $char; 
     } // foreach 
     // We've finished looping through the entire shortest_string. 
     // Remove the first char and start all over. Do this until there are no more 
     // chars to search on. 
     array_shift($shortest_string); 
    } 
    // If we made it here then we've run through everything 
    usort($longest_common_substring, $sort_by_strlen); 
    return array_pop($longest_common_substring); 
} 

我在我的博客上寫了一點點：

• Find the longest common substring using PHP（2011年2月24日）

Answer 6

我剛寫了一個功能存在於STR2 STR1最長的子串

public static function getLongestMatchingSubstring($str1, $str2) 
{ 
    $len_1 = strlen($str1); 
    $longest = ''; 
    for($i = 0; $i < $len_1; $i++){ 
     for($j = $len_1 - $i; $j > 0; $j--){ 
      $sub = substr($str1, $i, $j); 
      if (strpos($str2, $sub) !== false && strlen($sub) > strlen($longest)){ 
       $longest = $sub; 
       break; 
      } 
     } 
    } 
    return $longest; 
}