Longest common prefix (word by word)

In the given input set of strings, write a program to find the longest common prefix.

Examples

Input strings : {“code”, ”codex”, ”cosec”, ”coding”,”cobalt”}

Output : “co”

Time complexity : O(NM),

N = Number of strings
M = Length of longest string

Space complexity : O(M)

Algorithm

Here, we use associate property

LCP(s1, s2, s3) = LCP(LCP(s1, s2), s3)

1.  We create a function to find common prefix for two strings.
      a. Compare strings characters.
      b. Push them to result, if same.
      c. Return final result.

2. Make initial output_prefix as first element of input array.

3. Compare it to second it and store it in ouput_prefix and soon.

4. Return the final output_prefix.

C++ Program

#include <bits/stdc++.h>

using namespace std;
 
//function to find
//common prefix of two strings
string LCPUtil(string string1, string string2)
{
    string output;
    int length1 = string1.length(), length2 = string2.length();
    //Compare string1 and string2
    for (int i=0, j=0; (i<=length1-1) && (j<=length2-1); i++,j++)
    {
        if (string1[i] != string2[j])
        {
            break;
        }
        output.push_back(string1[i]); }
    return (output);
}
//Function to find LCP
//longest commmon prefix compare word by word 
string  LCP(string arr[], int n)
{
    string output_prefix =  arr[0];
    for (int i=1; i<=n-1; i++)
    {
        output_prefix = LCPUtil(output_prefix, arr[i]);
    }
    return (output_prefix);
}
 
 
//Main function
int main()
{
    string string_array[] = {"code","codex", "cosec", "coding","cobalt"};
    int length = sizeof(string_array)/sizeof(string_array[0]);
    string ans = LCP(string_array, length);
    if(ans.length())
    {
        cout<<"Longest common prefix is: "<<ans;
    }
    else
    {
        cout<<"No common prefix found";
    }
    return 0;
}
Try It

 


Next > < Prev
Scroll to Top