Geek Answers Handbook

The longest anagram search algorithm

Let's say that we have a dictionary of about 250,000 words. The algorithm should take 12 letters in the form of an array or a string and find a variation that matches the long word of the dictionary.

Of course, you can always rudely force him, but I wonder what would be the most elegant way to do this?

Responses to using languages โ€‹โ€‹other than PHP will also be accepted if they do not use any language-specific functions as a shortcut to the main problem.

Note. Words are stored in a database, but I can pull them into memory for speed. Although I'm not sure if indexing PHP is better than indexing a MySQL database?

+5
source share
5

. , "foobar" "abfoor".

, . , , . . ... ..

: "" . , 2 ^ n , n - ( : 12) (, ), , , .

+4

, .

:

   word varchar(12), 
   a int,
   b int, 
   c int,
    ...
   w int,
   z int;

a z , , , :

word,    a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z
anagram, 3,0,0,0,0,0,1,0,0,0,0,0,1,1,0,0,0,1,0,0,0,0,0,0,0,0

, , :

select word, length(word) as wordlen
from dictionary
where
a <= 4 and
b <= 0 and
c <= 1 and
d <= 2 and
e <= 0 and
f <= 0 and
 ....
z <= 0
order by wordlen desc;

, .

, ( ) .

, ,

+4

, , ,

+1

. #, .

, , , . "" , , , , ,

- .

+1

:

:

int_32 letter_mask
int_32 permutation_match_mask
if(((letter_mask XOR permutation_match_mask) AND letter_mask)  == 0)
        YOU_HAVE_HIT;

, , , ( , , ), leter permutationmatchmask

.

12 , , 4095 ( = 1- > 12 (12 i)) ( ABCD (ABCD, ABC, ABD, ACD, BCD, AB, AC, AD, BC, BD, CD, A, B, C, D) , , 4095 12 , .

4095 * Log2 (250000), aproximetly 75000. .

.

0

More articles:


All Articles