How can I find the Largest Common Substring between two strings in PHP?

Question

Is there a fast algorithm for finding the Largest Common Substring in two strings or is it an NPComplete problem?

In PHP, I can find a needle in a haystack:

<?php

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

I guess I could do this in a loop over one of the strings but that would be very expensive! 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).

Does anyone have any PHP code they can throw out there?

Answer 1

I have since found a relevant wikipedia article. It is not a NP complete problem, it can be done in O(mn) time using a dynamic programming algorithm.

In PHP I found the similar_text function very useful. Here's a code sample to retrieve a series of text emails and loop through them and find ones that are 90% similar to each other. Note: Something like this is NOT scalable:

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

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).

I think you should be looking at Bayesian spam inference algorithms, not necessarily longest common substring.

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

Answer 3

The similar_text function may be what you want.

This calculates the similarity between two strings. Returns the number of matching chars in both strings

You may also want to look at levenshtein

Answer 4

Please have a look at Algorithm implementation/Strings/Longest common substring on Wikibooks. I haven't tested the PHP implementation but it seems to match the general algorithm on the Wikipedia page.