如何在PHP中找到两个字符串之间的最大公共子串？

Question

是否存在一种快速算法,可以在两个中找到最大公共子串,strings还是一个NPComplete问题？

在PHP中,我可以在大海捞针中找到针:

<?php

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

我想我可以在其中一个循环中做到这一点,strings但这将是非常昂贵的!特别是因为我的应用是搜索电子邮件数据库并查找垃圾邮件(即同一个人发送的类似电子邮件).

有没有人有他们可以丢弃的PHP代码？

Answer 1

该similar_text功能可能是你想要的东西.

这计算两个字符串之间的相似性.返回两个字符串中匹配字符的数量

你可能也想看看levenshtein

Answer 2

特别是因为我的应用是搜索电子邮件数据库并查找垃圾邮件(即同一个人发送的类似电子邮件).

我认为你应该关注贝叶斯垃圾邮件推理算法,不一定是最长的常见子串.

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

Answer 3

我刚写了一个函数,找到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;
}

Answer 4

我后来找到了相关的维基百科文章。这不是一个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";
?>