Substring Search in a Map

[kirthiga.narayanan]

Hi,

I have a hash map with both the keys and the values as
strings...say emp id as the key and employee name as value.
eg: EMP1--->John Smith
EMP2---->AolSmith

Now I enter a search key say "Smith" or "th" or "S"
and I need to find out all the values in the map which contains the
search key. In the above examples, the values "John Smith" and
"AolSmith" have to be returned...

If the search Key is "h", then John Smith alone shud be returned...
Remember its a SUBSTRINGSEARCH.........
I can use Linear Search but when
the size of the map increases the performance decreases rapidly...
is there any other way to do it.......Please let me know ASAP.......
Even if means storing in a different data structure I dont mind....

Thanks
Kirthiga

 

[Roedy Green]

I have a hash map with both the keys and the values as
strings...say emp id as the key and employee name as value.
eg: EMP1--->John Smith
EMP2---->AolSmith

Now I enter a search key say "Smith" or "th" or "S"
and I need to find out all the values in the map which contains the
search key. In the above examples, the values "John Smith" and
"AolSmith" have to be returned...

If the search Key is "h", then John Smith alone shud be returned...
Remember its a SUBSTRINGSEARCH.........
I can use Linear Search but when
the size of the map increases the performance decreases rapidly...
is there any other way to do it.......Please let me know ASAP.......
Even if means storing in a different data structure I dont mind....

Your map goes looks for EMP1. You need a second TreeMap that goes the
other way. You need to massage your keys ahead of time to look like
"Smith John" so that you can look up with approximate key.

There is no substring search by key.. For that you need to scan the
entire set of keys linearly. Best to use an SQL engine that will
optimise such searches.

 

[Googmeister]

Hi,

I have a hash map with both the keys and the values as
strings...say emp id as the key and employee name as value.
eg: EMP1--->John Smith
EMP2---->AolSmith

Now I enter a search key say "Smith" or "th" or "S"
and I need to find out all the values in the map which contains the
search key. In the above examples, the values "John Smith" and
"AolSmith" have to be returned...

If the search Key is "h", then John Smith alone shud be returned...
Remember its a SUBSTRINGSEARCH.........
I can use Linear Search but when
the size of the map increases the performance decreases rapidly...
is there any other way to do it.......Please let me know ASAP.......
Even if means storing in a different data structure I dont mind....

You can form all of the suffixes and sort them (or put them
in a BST if you need to support insert/delete). Now,
you can use binary search to find any substring.

Here's the array for "johnsmith".

h
hnsmith
ith
johnsmith
mith
nsmith
ohnsmith
smith
th

When forming the suffixes, be sure to do it implicitly,
say using substring(), so that it takes only linear
space (and not quadratic!).

See also suffix arrays and suffix trees for
more sophisticated (and complicated) versions.