Given array A[] of strings of size N, the task for this problem is to print the Maximum Common prefix of string ‘i’ with other strings from 1 to N apart from ‘i’ itself for all given strings from 1 to N. Given strings consists of lowercase English letters.
Examples:
Input: {“abc”, “abb”, “aac”}
Output: 2 2 1
Explanation:
- Answer for first string is two. since first string has maximum length of common prefix is 2. with one of the all other strings.
- Answer for second string is two. since second string has maximum length of common prefix is 2 with one of the all other strings.
- Answer for third string is one. since third string has maximum length of common prefix is 1 with one of the all other strings.
Input: A2 = {“abracadabra”, “bracadabra”, “racadabra”, “acadabra”, “cadabra”, “adabra”, “dabra”, “abra”, “bra”, “ra”, “a”}
Output: 4 3 2 1 0 1 0 4 3 2 1
Naive approach: The basic way to solve the problem is as follows:
The basic way to solve this problem is to iterate all other strings for each strings and maintain maximum count.
Time Complexity: O(N2)
Auxiliary Space: O(N)
Efficient Approach: The above approach can be optimized based on the following idea:
Trie data structure can be used to solve this problem.
Follow the steps below to solve the problem:
- All strings are inserted in TRIE by iterating on each string from A[].
- Iterating on all strings from 1 to N.
- For each string remove that string by calling remove().
- Print a maximum length of string with whom the given string has the maximum common prefix by calling query().
- Insert the same string back again in TRIE by insert().
Below is the implementation for the above approach:
C++
// C++ code for the above approach:
#include <bits/stdc++.h>
using namespace std;
// Structure for Node of Trie
struct Node {
// Links of string trie
Node* links[26];
// Count of similar prefixes
// strings has
int cnt = 0;
};
// Root node initialized
Node* root = new Node();
// Insert fucntion for inserting
// words in trie
void insert(string word)
{
// Initializing node variable
Node* node = root;
// Iterating on given word
for (int i = 0; i < word.size(); i++) {
// If node does not exists
if (node->links[word[i] - 'a'] == NULL) {
// Creating new node
node->links[word[i] - 'a'] = new Node();
}
// Next node
node = node->links[word[i] - 'a'];
// Incrementing counter
node->cnt++;
}
}
// Remove function for removing
// words in trie
void remove(string word)
{
// Initialzingg node vaiable
Node* node = root;
// Iterating on given word
for (int i = 0; i < word.size(); i++) {
// Next node
node = node->links[word[i] - 'a'];
// Decrementing the counter
node->cnt--;
}
}
// Finding common prefix in all
// other strings
int query(string word)
{
// Count of answer
int cnt = 0;
// Initialzation of node variable
Node* node = root;
// Iterating on given word
for (int i = 0; i < word.size(); i++) {
// If doesn't exist break;
if (node->links[word[i] - 'a'] == NULL)
break;
// Next node
node = node->links[word[i] - 'a'];
// If counter zero break;
if (node->cnt == 0)
break;
// Incrementing the counter
cnt++;
}
// Returning the integer
return cnt;
}
// Function for finding Longest Common
// prefix of all given strings in given
// array
void findLCP(vector<string>& A, int N)
{
// Inserting all strings in Trie
for (int i = 0; i < N; i++)
insert(A[i]);
// Finding answer for ith string
for (int i = 0; i < N; i++) {
// Deleting current string from Trie
remove(A[i]);
// Printing answer for i'th string
cout << query(A[i]) << " ";
// Inserting i'th string again
insert(A[i]);
}
cout << endl
<< endl;
}
// Driver program to test above functions
int main()
{
vector<string> A1 = { "abc", "abb", "aac" };
int N1 = 3;
// Call for test case 1
findLCP(A1, N1);
vector<string> A2
= { "abracadabra", "bracadabra", "racadabra",
"acadabra", "cadabra", "adabra",
"dabra", "abra", "bra",
"ra", "a" };
int N2 = 11;
// Call for test case 2
findLCP(A2, N2);
return 0;
}
2 2 1 4 3 2 1 0 1 0 4 3 2 1
Time Complexity: O(N)
Auxiliary Space: O(N)
Related Articles:
Stay connected with us on social media platform for instant update click here to join our Twitter, & Facebook We are now on Telegram. Click here to join our channel (@TechiUpdate) and stay updated with the latest Technology headlines. For all the latest Technology News Click Here