# Find the longest common prefix (LCP) between given set of strings

Write an efficient algorithm to find the longest common prefix (LCP) between given set of strings.

For example,

Input:  technique, technician, technology, technical
Output: The longest common prefix is techn

Input:  techie delight, tech, techie, technology, technical
Output: The longest common prefix is tech

Simple solution is to consider each string one at a time, and calculate its longest common prefix with the longest common prefix of strings processed so far. The time complexity of this solution is O(N*M) where N is the number of words, and M is the maximum length of a word.

This is demonstrated below in C++:

Output:

The longest common prefix is tech

We can also use divide and conquer technique for finding the longest common prefix. Like all divide and conquer algorithms, the idea is to divide the group of strings into two smaller sets and then recursively process those sets. This is similar to merge-sort routine except for merging the two halves, we find the longest common prefix of both halves.

Output:

The longest common prefix is tech

The time complexity of above solution is O(N*M) where N is the number of words, and M is the maximum length of a word. The auxiliary space used is O(Mlog(N)) for the call stack.     (1 votes, average: 5.00 out of 5) Loading... 