Longest Common Prefix (LCP) Problem
Write an efficient algorithm to find the longest common prefix (LCP) between a given set of strings.
For example,
Output: The longest common prefix is techn
Input: techie delight, tech, techie, technology, technical
Output: The longest common prefix is tech
A simple solution is to consider each string 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 total number of words and M is the maximum length of a word.
This is demonstrated below in C++, Java, and Python:
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 41 |
#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 a given set of strings string findLCP(vector<string> const &words) { string prefix = words[0]; for (string s: words) { prefix = LCP(prefix, s); } return prefix; } 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
Java
|
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 |
import java.util.Arrays; import java.util.List; class Main { // Function to find the longest common prefix between two strings public static String LCP(String X, String Y) { int i = 0, j = 0; while (i < X.length() && j < Y.length()) { if (X.charAt(i) != Y.charAt(j)) { break; } i++; j++; } return X.substring(0, i); } // Function to find the longest common prefix (LCP) between a given set of strings public static String findLCP(List<String> words) { String prefix = words.get(0); for (String s: words) { prefix = LCP(prefix, s); } return prefix; } public static void main(String[] args) { List<String> words = Arrays.asList("techie delight", "tech", "techie", "technology", "technical"); System.out.println("The longest common prefix is " + findLCP(words)); } } |
Output:
The longest common prefix is tech
Python
|
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 |
# Function to find the longest common prefix between two strings def LCP(X, Y): i = j = 0 while i < len(X) and j < len(Y): if X[i] != Y[j]: break i = i + 1 j = j + 1 return X[:i] # Function to find the longest common prefix (LCP) between a given set of strings def findLCP(words): prefix = words[0] for s in words: prefix = LCP(prefix, s) return prefix if __name__ == '__main__': words = ['techie delight', 'tech', 'techie', 'technology', 'technical'] print('The longest common prefix is', findLCP(words)) |
Output:
The longest common prefix is tech
We can also use the Divide and Conquer technique for finding the longest common prefix (LCP). Like all divide-and-conquer algorithms, the idea is to divide the strings into two smaller sets and then recursively process those sets. This is similar to the merge sort routine, except we find the LCP of the two halves instead of merging both halves.
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 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 |
#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 a // given set of strings string findLCP(vector<string> const &words, int low, int high) { // base case: if `low` is more than `high`, 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 subproblems and recur for each subproblem 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); } 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
Java
|
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 55 |
import java.util.Arrays; import java.util.List; class Main { // Function to find the longest common prefix between two strings public static String LCP(String X, String Y) { int i = 0, j = 0; while (i < X.length() && j < Y.length()) { if (X.charAt(i) != Y.charAt(j)) { break; } i++; j++; } return X.substring(0, i); } // A recursive function to find the longest common prefix (LCP) between a // given set of strings public static String findLCP(List<String> words, int low, int high) { // base case: if `low` is more than `high`, return an empty string if (low > high) { return ""; } // base case: if `low` is equal to `high`, return the current string if (low == high) { return words.get(low); } // find the mid-index int mid = (low + high) / 2; // partition the problem into subproblems and recur for each subproblem 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); } public static void main(String[] args) { List<String> words = Arrays.asList("techie delight", "tech", "techie", "technology", "technical"); System.out.println("The longest common prefix is " + findLCP(words, 0, words.size() - 1)); } } |
Output:
The longest common prefix is tech
Python
|
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 |
# Function to find the longest common prefix between two strings def LCP(X, Y): i = j = 0 while i < len(X) and j < len(Y): if X[i] != Y[j]: break i = i + 1 j = j + 1 return X[:i] # A recursive function to find the longest common prefix (LCP) between a # given set of strings def findLCP(words, low, high): # base case: if `low` is more than `high`, return an empty string if low > high: return '' # base case: if `low` is equal to `high`, return the current string if low == high: return words[low] # find the mid-index mid = (low + high) // 2 # partition the problem into subproblems and recur for each subproblem X = findLCP(words, low, mid) Y = findLCP(words, mid + 1, high) # return the longest common prefix of strings `X` and `Y` return LCP(X, Y) if __name__ == '__main__': words = ['techie delight', 'tech', 'techie', 'technology', 'technical'] print('The longest common prefix is', findLCP(words, 0, len(words) - 1)) |
Output:
The longest common prefix is tech
The time complexity of the above solution is O(N.M), where N is the total number of words and M is the maximum length of a word. The auxiliary space used is O(M.log(N)) for the call stack.
Also See:
Longest Common Prefix in a given set of strings (Using Trie)
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)