Come posso trovare la più grande sottostringa comune tra due stringhe in PHP?

Question

Esiste un algoritmo rapido per la ricerca della più grande sottostringa comune in due strings o si tratta di un problema NPompleto?

In PHP riesco a trovare un ago in un pagliaio:

<?php 

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

Credo che avrei potuto fare questo in un ciclo su uno dei strings ma che sarebbe molto costoso! Soprattutto perché la mia applicazione è cercare un database di e-mail e cercare spam (ad esempio email simili inviate dalla stessa persona).

Qualcuno ha un codice PHP che può buttare lì?

Answer 1

Da allora ho trovato a relevant wikipedia article. Non è un problema NP completo, può essere fatto in tempo O (mn) usando un algoritmo di programmazione dinamica.

In PHP ho trovato molto utile la funzione similar_text. Ecco un esempio di codice per recuperare una serie di e-mail di testo e passarle in loop e trovare quelle che sono il 90% simili tra loro. Nota: Qualcosa di simile non è scalabile:

<?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

Tanto più che la mia domanda di questo è di cercare un database di e-mail e cercare di spam (ossia messaggi di posta elettronica inviati simili dalla stessa persona).

Penso che dovresti esaminare gli algoritmi di inferenza dello spam bayesiano, non necessariamente la più lunga sottostringa comune.

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

Answer 3

La funzione similar_text può essere quello che vuoi.

Questo calcola la somiglianza tra due stringhe. Restituisce il numero di caratteri corrispondenti in entrambe le stringhe

Si potrebbe anche voler guardare levenshtein

Answer 4

Si prega di dare un'occhiata al Algorithm implementation/Strings/Longest common substring su Wikibooks. Non ho testato l'implementazione di PHP ma sembra corrispondere all'algoritmo generale sulla pagina di Wikipedia.

Answer 5

tardi per questo partito, ma qui è un modo per trovare il più grande sottostringa comune in un array di stringhe:

Esempio:

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

La funzione:

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); 
} 

I ho scritto un po 'sul mio blog:

• Find the longest common substring using PHP (24 Feb 2011)

Answer 6

Ho appena scritto una funzione i reperti la stringa sub più lunga str1 che esiste in str2

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; 
}