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

php algorithm string performance spam-prevention
Tom picture Tom · Dec 3, 2008 · Viewed 14.8k times · Source

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

Zoredache picture Zoredache · Dec 3, 2008

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

Related questions

How to generate all permutations of a string in PHP?

I need an algorithm that return all possible combination of all characters in one string. I've tried: $langd = strlen($input); for($i = 0;$i < $langd; $i++){ $tempStrang = NULL; $tempStrang .= substr($input, $i, 1); for($j = $i+1, $k=0; $k < $langd; $k++, $…

Read More
List of Big-O for PHP functions

After using PHP for a while now, I've noticed that not all built-in PHP functions are as fast as expected. Consider these two possible implementations of a function that finds if a number is prime using a cached array of …

Read More
Algorithm to get the excel-like column name of a number

I'm working on a script that generate some Excel documents and I need to convert a number into its column name equivalent. For example: 1 => A 2 => B 27 => AA 28 => AB 14558 => UMX I have already written an algorithm …

Read More