# Find longest matching key

#### Do you have a question? Post it now! No Registration Necessary.  Now with pictures!

•  Subject
• Author
• Posted on
Hello,

I have two arrays like this:

\$aSearch = array( 'A', 'B', 'C.D', 'E', 'F' );
\$aSubject = array( 'A' => 0, 'A.B' => 1, 'X' => 2, 'C.D.E' => 3, 'A.B.C' =>
4 );

Now I want to search \$aSubject for the longest key that consists of the
first x elements of \$aSearch concatenated by "." (where x = 1...count(
\$aSearch ) ). In other words, he algorithm involved should check for the
existence of the following keys in \$aSubject:

A
A.B
A.B.C.D
A.B.C.D.E
A.B.C.D.E.F

and return the longest match - in the example 'A.B'. Now I could first
create an array of all keys to search for and then loop through them to find
a match in \$aSubject, but I wonder if there is a more efficient, more
elegant solution. There doesn't seem to be any PHP function that could help
with this specific problem.

Greetings,
Thomas

--
C'est pas parce qu'ils sont nombreux à avoir tort qu'ils ont raison!
(Coluche)

## Re: Find longest matching key

Thomas Mlynarczyk wrote:

foreach (\$aSearch as \$a)
{
\$key = \$a;
while (strlen(\$key) && !isset(\$aSubject[\$key]))
\$key = preg_replace('/\.?[^\.]*\$/', '', \$key);

if (strlen(\$key))
printf("Searched for '%s'. Closest match was '%s', value %s.\n",
\$a,
\$key,
\$aSubject[\$key]);
else
printf("Searched for '%s'. No matching key found.\n", \$a);
}

A bit cleaner to use a function:

function array_component_search (\$needle, &\$haystack, &\$value=NULL)
{
\$key = \$needle;
while (strlen(\$key) && !isset(\$haystack[\$key]))
\$key = preg_replace('/\.?[^\.]*\$/', '', \$key);

\$value = strlen(\$key) ? \$haystack[\$key] : NULL;

return strlen(\$key) ? \$key : FALSE;
}
foreach (\$aSearch as \$a)
{
\$key = array_component_search(\$a, \$aSubject, \$value);

if (\$key!==FALSE)
printf("Searched for '%s'. Closest match was '%s', value %s.\n",
\$a,
\$key,
\$value);
else
printf("Searched for '%s'. No matching key found.\n", \$a);
}

Note that array_component_search takes two required arguments:

\$needle = Key you're searching for a close match for.
\$haystack = Lookup array.

The closest matching key is returned by the function, and as a side-effect,
the value for that key may be placed in a variable passed to the function
as a third argument.

--
Toby A Inkster BSc (Hons) ARCS
[Geek of HTML/SQL/Perl/PHP/Python/Apache/Linux]
[OS: Linux 2.6.12-12mdksmp, up 11 days, 1:11.]

Belgium
http://tobyinkster.co.uk/blog/2007/11/17/belgium/

## Re: Find longest matching key

Also sprach Toby A Inkster:

This finds \$aSubject['A'], but should find \$aSubject['A.B'].
If I remove the foreach and put an
\$a = implode( '.', \$aSearch )
at the beginning, it will find \$aSubject['A.B.C']. (Because, in the imploded
form, the information that 'C.D' is "indivisible" gets lost.)

Maybe I was not clear enough describing my problem. The algorithm should be
something equivalent to

\$aSearch = array( 'A', 'B', 'C.D', 'E', 'F' );
\$aSubject = array( 'A' => 0, 'A.B' => 1, 'X' => 2, 'C.D.E' => 3, 'A.B.C' =>
4 );

1)
Convert \$aSearch somehow to
\$aSearch =array(
'A.B.C.D.E.F',
'A.B.C.D.E',
'A.B.C.D',
'A.B',           // Note: no 'A.B.C', as 'C.D' is "indivisible"
'A'
)

2)
foreach ( \$aSearch as \$sKey )
{
if ( array_key_exists( \$sKey, \$aSubject ) ) { echo "Found
\$aSubject[\$sKey]"; break; }
}

Meanwhile I've come up with this:

for ( \$tmp = array(), \$i = 0; \$i < count( \$aSearch ); \$i++ )
{
\$tmp[\$i] = \$i ? \$tmp[ \$i - 1 ] . '.' . \$aSearch[\$i] : \$aSearch[\$i];
}

foreach ( array_reverse( \$tmp, true ) as \$sKey )
{
if ( array_key_exists( \$sKey, \$aSubject ) ) { echo "Found
\$aSubject[\$sKey]"; break; }
}

But it does not look elegant/efficient enough to me.

Greetings,
Thomas

--
C'est pas parce qu'ils sont nombreux à avoir tort qu'ils ont raison!
(Coluche)

## Re: Find longest matching key

On Nov 17, 6:13 pm, "Thomas Mlynarczyk" <tho...@mlynarczyk-
webdesign.de> wrote:

...
...

function longestMatchingKey (\$aSrch, \$aSubj) {
if (array_key_exists(\$k=implode(".", \$aSrch), \$aSubj)) return \$k;
for (\$i=sizeof(\$aSrch);\$k=substr(\$k,0,-strlen(\$aSrch[--\$i])-1);)
if (array_key_exists(\$k, \$aSubj)) break;
return \$k; }

(5 lines total, one loop, no reversing, watch for wrapping) Though
perhaps not overly different from what you suggested...
Csaba Gabor from Vienna

## Re: Find longest matching key

Also sprach Csaba Gabor:

Maybe not overly different, but certainly much more efficient and elegant!
Thanks a lot! :-)

Greetings,
Thomas

--
C'est pas parce qu'ils sont nombreux à avoir tort qu'ils ont raison!
(Coluche)