Как я могу найти самую большую общую подстроку между двумя строками в PHP?

Есть ли быстрый алгоритм поиска наибольшей общей подстроки в двух strings или это проблема NPComplete?

В PHP я могу найти иголку в стоге сена:

<?php

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

Думаю, я мог бы сделать это в цикле через один из strings, но это было бы очень дорого! Тем более, что я использую это для поиска в базе данных электронной почты и поиска спама (т. Е. Похожих писем, отправленных одним и тем же человеком).

Есть ли у кого-нибудь какой-нибудь PHP-код, который они могут там выбросить?

Стоит ли изучать PHP в 2023-2024 годах?
Стоит ли изучать PHP в 2023-2024 годах?
Привет всем, сегодня я хочу высказать свои соображения по поводу вопроса, который я уже много раз получал в своем сообществе: "Стоит ли изучать PHP в...
Symfony Station Communiqué - 7 июля 2023 г
Symfony Station Communiqué - 7 июля 2023 г
Это коммюнике первоначально появилось на Symfony Station .
Оживление вашего приложения Laravel: Понимание режима обслуживания
Оживление вашего приложения Laravel: Понимание режима обслуживания
Здравствуйте, разработчики! В сегодняшней статье мы рассмотрим важный аспект управления приложениями, который часто упускается из виду в суете...
Установка и настройка Nginx и PHP на Ubuntu-сервере
Установка и настройка Nginx и PHP на Ubuntu-сервере
В этот раз я сделаю руководство по установке и настройке nginx и php на Ubuntu OS.
Коллекции в Laravel более простым способом
Коллекции в Laravel более простым способом
Привет, читатели, сегодня мы узнаем о коллекциях. В Laravel коллекции - это способ манипулировать массивами и играть с массивами данных. Благодаря...
Как установить PHP на Mac
Как установить PHP на Mac
PHP - это популярный язык программирования, который используется для разработки веб-приложений. Если вы используете Mac и хотите разрабатывать...
19
0
14 797
6
Перейти к ответу Данный вопрос помечен как решенный

Ответы 6

Ответ принят как подходящий

С тех пор я нашел соответствующая статья в Википедии. Это не полная проблема NP, ее можно решить за время O (mn), используя алгоритм динамического программирования.

В PHP я нашел очень полезной функцию подобный_текст. Вот пример кода для получения серии текстовых сообщений электронной почты и их просмотра, чтобы найти те, которые на 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";
?>

Especially since my application of this is to search a database of email and look for spam (i.e. similar emails sent by the same person).

Я думаю, вам следует обратить внимание на байесовские алгоритмы вывода спама, а не на самую длинную общую подстроку.

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

Функция подобный_текст может быть тем, что вам нужно.

Это вычисляет сходство между двумя строками. Возвращает количество совпадающих символов в обеих строках.

Вы также можете посмотреть Левенштейн

нет, он не этого хочет. эти алгоритмы вообще не вычисляют самую длинную общую подстроку, почему вы даже предлагаете это?

nights 12.05.2017 08:45

Пожалуйста, посмотрите Реализация алгоритма / Строки / Самая длинная общая подстрока в Викиучебниках. Я не тестировал реализацию PHP, но, похоже, она соответствует общему алгоритму на странице Википедии.

К тому же это невероятно медленно. Алгоритм динамического программирования, перечисленный на странице wikipedia Longest_common_substring_problem, очень экономичен, но при реализации на php он более чем в два раза медленнее, чем хорошо написанное решение грубой силы, например Решение @ Chrisbloom7 ниже.

Benubird 12.04.2013 13:27

Поздно к этой вечеринке, но вот способ найти самую большую общую подстроку в массиве строк:

Пример:

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

Я немного написал об этом в своем блоге:

Эта функция переводит вывод в нижний регистр !! Имейте в виду. Есть другие алгоритмы решения этой проблемы, которые не страдают от этой проблемы.

Flip 07.03.2019 04:40

Я только что написал функцию, которая находит самую длинную подстроку в str1, которая существует в 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;
}

Это не так быстро, как подход динамического программирования (en.wikibooks.org/wiki/Algorithm_Implementation/Strings/…), но он использует гораздо меньше памяти. В моем тесте подход DP разбил мой PHP при сравнении двух 1200-символьных строк. Даже если я выделю больше памяти, это будет всего в 6 раз медленнее для той же работы (6 секунд против 1 секунды).

Ben 18.12.2016 02:44

В моем тесте эта реализация может быть до 1000 !!! так же медленно, как и другие алгоритмы (особенно с длинными строками). Имейте в виду.

Flip 07.03.2019 04:27

Другие вопросы по теме