una - ¿Cómo puedo encontrar la subcadena común más grande entre dos cadenas en PHP?

strpos php

Question

¿Hay un algoritmo rápido para encontrar la subcadena común más grande en dos strings o es un problema NPComplete?

En PHP puedo encontrar una aguja en un pajar:

<?php

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

¡Creo que podría hacer esto en un ciclo sobre uno de los strings pero eso sería muy caro! Especialmente porque mi aplicación de esto es buscar en una base de datos de correo electrónico y buscar correo no deseado (es decir, correos electrónicos similares enviados por la misma persona).

¿Alguien tiene algún código PHP que puedan lanzar allí?

Answer 1

Especialmente porque mi aplicación de esto es buscar en una base de datos de correo electrónico y buscar correo no deseado (es decir, correos electrónicos similares enviados por la misma persona).

Creo que deberías buscar algoritmos de inferencia Bayesianos de spam, no necesariamente la subcadena común más larga.

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

Answer 2

Eche un vistazo a la implementación Algorithm / Strings / La subcadena común más larga en Wikilibros. No he probado la implementación de PHP, pero parece coincidir con el algoritmo general en la página de Wikipedia.

Answer 3

La función similar_text puede ser lo que quieras.

Esto calcula la similitud entre dos cadenas. Devuelve el número de caracteres coincidentes en ambas cadenas

También es posible que desee mirar levenshtein

Answer 4

Desde entonces he encontrado un artículo de wikipedia relevante . No es un problema completo de NP, se puede hacer en el tiempo O (mn) usando un algoritmo de programación dinámica.

En PHP encontré la función similar_text muy útil. Aquí hay un ejemplo de código para recuperar una serie de correos electrónicos de texto y recorrerlos y encontrar los que son 90% similares entre sí. Nota: algo como esto NO es escalable :

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

Acabo de escribir una función que encuentra la cadena secundaria más larga en str1 que existe en 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;
}

Answer 6

Tarde a esta fiesta, pero aquí hay una manera de encontrar la subcadena común más grande en una serie de cadenas:

Ejemplo:

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

La función:

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

He escrito esto un poco en mi blog:

• Encuentre la subcadena común más larga utilizando PHP (24 de febrero de 2011)