Longest Common Prefix Word by Word Matching

Difficulty Level Hard
Frequently asked in Adobe Amazon Apple Bloomberg eBay Facebook Google Microsoft VMware Yahoo
StringViews 1661

Problem Statement

In the “Longest Common Prefix using Word by Word Matching” problem, we have given N strings.  Write a program to find the longest common prefix of the given strings.

Input Format

The first line containing an integer value N which denotes the number of strings.

Next N lines containing a string.

Output Format

The first and only one line containing a string “ans” which is our Longest Common Prefix of the given N strings. If no such prefix exist then print -1.

Constraints

  • 1<=|N|<=10^3
  • 1<=|s[i]|<=10^3 where i from 0 to N-1
  • s[i][j] must be a lower case English alphabet where i from 0 to N-1, and j from 0 to |s[i]|.

Example

5
abcde 
abba 
abaa 
abbbbb 
ababab
ab

Explanation: Here we can see the common prefix of the 1st and second string is “ab”. Now check this prefix with every string one by one and get the final prefix which is “ab”.

Algorithm

Here, we use associate property – LCP(s1, s2, s3) = LCP(LCP(s1, s2), s3). To employ this idea, the algorithm iterates through the strings [S1…Sn], finding at each iteration  the longest common prefix of strings  When  is an empty string, the algorithm ends. Otherwise, after n iterations, the algorithm returns .

1.  We create a function to find a common prefix for two strings.

  • Compare strings characters.
  • Push them to result, if same.
  • Return final result.

2. Make the initial output_prefix as the first element of the input string.

3. Compare it to the second it and store it in ouput_prefix and so on.

4. Return the final output_prefix.

Implementation

C++ Program for Longest Common Prefix Word by Word Matching

#include <bits/stdc++.h>
using namespace std;
 
string prefix(string s, string t)
{
    string res;
    int n = s.length();
    int m = t.length();
    for(int i=0,j=0;(i<=n-1)&&(j<=m-1);i++,j++)
    {
        if(s[i]!=t[j])
        {
            break;
        }
        res.push_back(s[i]); 
    }
    return res;
}

string  common_prefix(vector<string> v)
{
    string res=v[0];
    for(int i=1;i<=v.size()-1;i++)
    {
        res=prefix(res,v[i]);
    }
    return res;
}
 
int main()
{
    int n;
    cin>>n;
    vector<string> v;
    for(int i=0;i<n;i++)
    {
        string x;
        cin>>x;
        v.push_back(x);
    }
    string ans = common_prefix(v);
    if(ans.length())
    {
        cout<<ans<<endl;
    }
    else
    {
        cout<<-1<<endl;
    }
    return 0;
}

Java Program for Longest Common Prefix Word by Word Matching

import java.util.Scanner;
import java.util.Vector;

class sum
{
    public static String prefix(String s, String t)
    {
        String res="";
        int n = s.length();
        int m = t.length();
        for(int i=0,j=0;(i<n)&&(j<m);i++,j++)
        {
            if(s.charAt(i)!=t.charAt(j))
            {
                j=m;
            }
            else
            {
                res+=(s.charAt(i));
            } 
        }
        return res;
    }
    public static String common_prefix(Vector<String> v)
    {
        String res=v.get(0);
        for(int i=1;i<=v.size()-1;i++)
        {
            res=prefix(res, v.get(i));
        }
        return res;
    }
    public static void main(String[] args)
    {
        Scanner sr = new Scanner(System.in);
        int n=sr.nextInt();
        Vector<String> v = new Vector<String>(n+1);
        for(int i=0;i<n;i++)
        {
            String x = sr.next();
            v.add(x);
        }
        String ans = common_prefix(v);
        if(ans.length()!=0)
        {
            System.out.println(ans);
        }
        else
        {
            System.out.println("-1");
        }
    }
}




5 
abcde 
abba 
abaa 
abbbbb 
ababab
ab

Complexity Analysis for Longest Common Prefix Word by Word Matching

Time Complexity

O(n*m) where n is the total number of strings and m is the length of the maximum string.

Space Complexity

O(m) for store the common prefix after performing an operation between two strings.

Translate »