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

一尘不染

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

algorithm

是否有一种快速算法可以找到两个最大的公共子字符串，strings或者这是一个NPComplete问题？

在PHP中，我可以找到大海捞针：

<?php

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

我想我可以在之一上循环进行此操作，strings但这将非常昂贵！特别是由于我的应用程序是搜索电子邮件数据库并查找垃圾邮件（即同一个人发送的类似电子邮件）。

有没有人可以扔在那里的任何PHP代码？

阅读 206

2020-07-28

共1个答案

一尘不染

此后，我找到了相关的维基百科文章。这不是NP完全问题，可以使用动态编程算法在O（mn）时间内完成。

在PHP中，我发现like_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";
?>

2020-07-28