Table of Contents
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.