Q:

Most efficient algorithm to parse and compare string keys in java

I have the following Set<String> objects.
 "A_B_C_D_E_F_G",
 "A_B_C_D_E_X_G",
 "A_B_C_D_E_Z_G",
 "A_B_C_X_Y_F_G",
 "P_B_C_D_E_F_G",
 "A_C_N_D_E_F_G"
 ... and 10,000 more

Each String is a underscore separated list of unique ids. So to help you understand you can think of each string like this:
 String[] uniqueIds = string.split("_");

What I want to do is put each String into a Collection<String> where the Strings are grouped together if only one uniqueId is different, and the difference occurs in the same 'column'.
So if we looped through the Set<String> objects in the example shown above the following groupings would occur
Group1
 "A_B_C_D_E_F_G",
 "A_B_C_D_E_X_G", (because X is different than F)
 "A_B_C_D_E_Z_G", (because Z is different than F, and because Z and X are 
                   in the same column)

Group2
 "P_B_C_D_E_F_G", (because P is different than A, and is not the same column as 
                   in Group1)

Group3
 "A_B_C_X_Y_F_G", (because X is different than D, and is not the same column as 
                   in Group1 or Group2)
                  (because Y is different than E, and is not the same column as 
                   in Group1 or Group2)
Group4
 "A_C_N_D_E_F_G", (because C is different than B, and is not the same column as 
                   in Group1 or Group2 or Group 3)
                  (because N is different than C, and is not the same column as 
                   in Group1 or Group2 or Group 3)

I am trying to figure out the most efficient way of creating these groupings.  
My initial guess would be to start with an empty Map<someKey,Collection<String>>.
Then loop through the Set<String>, split each String into a uniqueId array and go through the Map looking for someKey which would would tell if that String belongs in the current collection, or goes into a new collection with a different someKey.  Defining what someKey is may be a bit tricky...maybe it would be a underscore separated list of the column numbers which values that have changed since the first String?
Since each String contains a lot of uniqueIds and the Set<String> size can be 10,000 it would seem that this algorithm can get slow quick.
Any suggestions?
Thanks!
UPDATE:::
There are cases where a String can fit into more than 1 group.  If that is the case, it would just be placed into the first available group that meets the criteria.

A:

First I have to say I'm not an algorithm expert.
But maybe you should try taking a look at
1) The Algorithm Design Manual by Steven Skiena - he has many solutions for common problem
2) Using a Tree where letters are the Node-values. Maybe you could somehow try a suffix tree: http://en.wikipedia.org/wiki/Suffix_tree The article says it is popular for many string operations. If you take a look at the "Applications" section in the article it really seems to fit :) And it runs in linear time.
To find the group a string belongs to, you can simply walk along the tree and look up until which degree a string matches and where it doesn't. (My intention)

