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

Question

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

在 PHP 中我可以大海捞针:

<?php

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

我想我可以在其中一个 strings 上循环执行此操作，但那会非常昂贵!特别是因为我对此的应用是搜索电子邮件数据库并查找垃圾邮件(即同一个人发送的类似电子邮件)。

有没有人有任何可以扔掉的 PHP 代码？

Answer 1

similar_text功能可能是你想要的。

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

您可能还想看看 levenshtein