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

**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++:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
#include <iostream> #include <vector> #include <string> using namespace std; // Function to find the longest common prefix between two strings string LCP(string X, string Y) { int i = 0, j = 0; while (i < X.length() && j < Y.length()) { if (X[i] != Y[j]) break; i++, j++; } return X.substr(0, i); } // Function to find the longest common prefix (LCP) between given set of strings string findLCP(vector<string> const &words) { string prefix = words[0]; for (string s: words) prefix = LCP(prefix, s); return prefix; } // main function int main() { vector<string> words { "techie delight", "tech", "techie", "technology", "technical" }; cout << "The longest common prefix is " << findLCP(words); return 0; } |

`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.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 |
#include <iostream> #include <vector> #include <string> using namespace std; // Function to find the longest common prefix between two strings string LCP(string X, string Y) { int i = 0, j = 0; while (i < X.length() && j < Y.length()) { if (X[i] != Y[j]) break; i++, j++; } return X.substr(0, i); } // A recursive function to find the longest common prefix (LCP) between // given set of strings string findLCP(vector<string> const &words, int low, int high) { // base case: if low is more than high index, return an empty string if (low > high) return string(""); // base case: if low is equal to high, return the current string if (low == high) return words[low]; // find the mid index int mid = (low + high) / 2; // partition the problem into sub-problems and recur for each sub-problem string X = findLCP(words, low, mid); string Y = findLCP(words, mid + 1, high); // return the longest common prefix of strings X and Y return LCP(X, Y); } // main function int main() { vector<string> words { "techie delight", "tech", "techie", "technology", "technical" }; cout << "The longest common prefix is " << findLCP(words, 0, words.size() - 1); return 0; } |

`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.

Longest Common Prefix in given set of strings (using Trie)

**Thanks for reading.**

Please use our online compiler to post code in comments. To contribute, get in touch with us.

Like us? Please spread the word and help us grow. Happy coding 🙂

## Leave a Reply