435,361 Members | 3,185 Online
Need help? Post your question and get tips & solutions from a community of 435,361 IT Pros & Developers. It's quick & easy.

# Find longest matching key

 P: n/a 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) Nov 17 '07 #1
4 Replies

 P: n/a Thomas Mlynarczyk wrote: 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'. 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. Helpful? -- 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.] [Now Playing: ./stereophonics/handbags_and_gladrags.ogg.] Belgium http://tobyinkster.co.uk/blog/2007/11/17/belgium/ Nov 17 '07 #2

 P: n/a Also sprach Toby A Inkster: 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); } 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) Nov 17 '07 #3

 P: n/a On Nov 17, 6:13 pm, "Thomas Mlynarczyk"

 P: n/a Also sprach Csaba Gabor: 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... 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) Nov 18 '07 #5

### This discussion thread is closed

Replies have been disabled for this discussion.