6

What algorithm would you suggest to find out the longest common prefixes of a list of strings?

I might have strings such as:

Call Mike and schedule meeting.
Call Lisa
Call Adam and ask for quote.
Implement new class for iPhone project
Implement new class for Rails controller
Buy groceries

I want to find out the following prefixes:

"Call "
"Implement new class "

I'll be using Objective C, so a ready made cocoa solution would be a plus (though not a must).

2
  • So you want all strings s such that s is a common prefix of two strings in the list, and s is not a strict substring of any other common prefix of the same two strings, and s is not the empty string? What about {"a1", "a2", "ab1", "ab2"}, do you want "a" or not? Jul 11, 2011 at 8:41
  • Yes, that's correct. And no, I don't need a.
    – cfischer
    Jul 11, 2011 at 8:44

4 Answers 4

6

Edit: for the clarified question:

  1. Sort the strings
  2. Find the longest common prefix of each adjacent pair
  3. Sort and dedupe the common prefixes, then remove any that's a strict prefix of another.

Actually, step (3) only requires that you remove any that's a dupe/prefix of another, which you could do with a trie or whatever instead of sorting. In fact it may be that the whole thing can be done faster with a suitably annotated trie - if you include a "count" at each node then you're looking precisely for nodes with a count of 2+, that have no children with a count of 2+.

But sorting is built in, and once you've sorted you can detect prefixes by looking at adjacent items, so it's probably less effort.

[Original answer:

Just a one-off operation, find the longest common prefix between all the strings?

I'd probably do it in terms of the length of the prefix. In pseudo-code, and assuming nul-terminated strings:

prefixlen = strlen(first_string);
foreach string in the list {
    for (i = 0; i < prefixlen; ++i) {
        if (string[i] != first_string[i]) {
            prefixlen = i;
            break;
        }
    }
    if (prefixlen == 0) break;
}

common_prefix = substring(firststring, 0, prefixlen);

]

5
  • 1
    +1, if it's a one time operation, using a trie incurs in a time/space penalty.
    – abeln
    Jul 9, 2011 at 16:15
  • Also, if the input strings happen to be in sorted order, you only need to compare the first and last strings. Jul 10, 2011 at 5:59
  • This is not exactly what I need. I don't need the single longest common prefix of n strings. Rather I need the m longest common prefixes for n strings.
    – cfischer
    Jul 11, 2011 at 8:17
  • @Fernando: could you define what it is that you need, then? Jul 11, 2011 at 8:25
  • For Objective-C in specific, be sure to look at -[NSString commonPrefixWithString:options:] for comparing individual strings, and NSMutableSet for easily weeding out strict duplicates. Sep 27, 2011 at 20:25
3

You could insert all your strings into a trie (aka prefix tree). Then traverse the trie from the root until you find a node with more than one child (or just stop inserting strings when you would have to append a second child to a node).

6
  • So if the first string is "a", and the second string is "b", I still have to insert the other 43 million strings into the trie? ;-p Jul 9, 2011 at 11:53
  • Pedantically I'd say, "move on to the next string" rather than "stop inserting strings" when you reach a branch point. The latter might suggest stop altogether, as opposed to "when inserting strings, stop inserting (that string) when...". But I know what you mean. Jul 9, 2011 at 11:57
  • There might be hundreds of strings (though probably less), but not thousands or millions.
    – cfischer
    Jul 9, 2011 at 11:58
  • @Fernando: but you still might like to exit early when possible. Running over a few hundred short strings won't take long, but it's not difficult to check for differences as you go, rather than at the end. Jul 9, 2011 at 11:59
  • Wouldn't moving on to the next string mean that you'd continue to add other strings to the trie, even though at this point you could be sure that the longest common prefix is the empty string?
    – omz
    Jul 9, 2011 at 12:00
2

That depends on what you are willing to consider a prefix.

I suppose the generic answer is to create a Trie (perhaps a suffix tree) that stores all strings into a n-ary tree. See http://en.wikipedia.org/wiki/Trie

enter image description here

Depending on your criteria for 'prefix' (say, n characters) you could select all nodes of rank n that have more than one children.

You'll have your list of repeated prefixes.

0
  1. Insert all the strings into a Trie data structure.
  2. DFS from the root to find the first node which has more than 1 edge going out of it.
  3. the path from root to the node computed in step 2 gives the longest common prefix for all the set of the strings.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.