Maximum common prefix of all strings
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 function 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) { // Initializing node variable 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; // Initialization 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; } // 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; } |
Java
// Java code for the above approach: import java.util.*; // Structure for Node of Trie class Node { // Links of string trie Node[] links = new Node[ 26 ]; // Count of similar prefixes strings has int cnt = 0 ; } public class Main { // Root node initialized static Node root = new Node(); // Insert function for inserting words in trie static void insert(String word) { // Initializing node variable Node node = root; // Iterating on given word for ( int i = 0 ; i < word.length(); i++) { // If node does not exists if (node.links[word.charAt(i) - 'a' ] == null ) { // Creating new node node.links[word.charAt(i) - 'a' ] = new Node(); } // Next node node = node.links[word.charAt(i) - 'a' ]; // Incrementing counter node.cnt++; } } // Remove function for removing words in trie static void remove(String word) { // Initializing node vaiable Node node = root; // Iterating on given word for ( int i = 0 ; i < word.length(); i++) { // Next node node = node.links[word.charAt(i) - 'a' ]; // Decrementing the counter node.cnt--; } } // Finding common prefix in all other strings static int query(String word) { // Count of answer int cnt = 0 ; // Initialization of node variable Node node = root; // Iterating on given word for ( int i = 0 ; i < word.length(); i++) { // If doesn't exist break; if (node.links[word.charAt(i) - 'a' ] == null ) break ; // Next node node = node.links[word.charAt(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 static void findLCP(List<String> A, int N) { // Inserting all strings in Trie for ( int i = 0 ; i < N; i++) insert(A.get(i)); // Finding answer for ith string for ( int i = 0 ; i < N; i++) { // Deleting current string from Trie remove(A.get(i)); // Printing answer for i'th string System.out.print(query(A.get(i)) + " " ); // Inserting i'th string again insert(A.get(i)); } System.out.println(); } // Driver program to test above functions public static void main(String[] args) { List<String> A1 = Arrays.asList( "abc" , "abb" , "aac" ); int N1 = 3 ; // Call for test case 1 findLCP(A1, N1); List<String> A2 = Arrays.asList( "abracadabra" , "bracadabra" , "racadabra" , "acadabra" , "cadabra" , "adabra" , "dabra" , "abra" , "bra" , "ra" , "a" ); int N2 = 11 ; // Call for test case 2 findLCP(A2, N2); } } // This code is contributed by rutikbhosale |
Python3
# Python3 code for the above approach class Node: def __init__( self ): # links of string trie self .links = [ None ] * 26 # count of similar prefixes strings has self .cnt = 0 # root node initialize root = Node() # Function for inserting words in trie def insert(word): # initialize node node = root # iterate on word for i in range ( len (word)): # if node not exist if not node.links[ ord (word[i]) - ord ( 'a' )]: # creating new node node.links[ ord (word[i]) - ord ( 'a' )] = Node() # next node node = node.links[ ord (word[i]) - ord ( 'a' )] # increase count by 1 node.cnt + = 1 # Function for removing words in trie def remove(word): # initialize node variable node = root # iterate on given word for i in range ( len (word)): # next node node = node.links[ ord (word[i]) - ord ( 'a' )] # decrease the count by 1 node.cnt - = 1 def query(word): # initialize count to 0 cnt = 0 # initialize node node = root # iterate for word for i in range ( len (word)): # if it doesn't exist break loop if not node.links[ ord (word[i]) - ord ( 'a' )]: break # next node node = node.links[ ord (word[i]) - ord ( 'a' )] # if counter zero break if node.cnt = = 0 : break # increase the count by 1 cnt + = 1 # return count return cnt # Function for finding Longest Common # prefix of all given strings for given array def findLCP(A): # insert all strings in trie for word in A: insert(word) # find answer for i-th string for word in A: # delet current string from trie remove(word) # print answer for i-th string print (query(word), end = " " ) # insert i-th string again insert(word) print () # Drive code A1 = [ "abc" , "abb" , "aac" ] # Function call for test case 1 findLCP(A1) A2 = [ "abracadabra" , "bracadabra" , "racadabra" , "acadabra" , "cadabra" , "adabra" , "dabra" , "abra" , "bra" , "ra" , "a" ] # Function call for test case 2 findLCP(A2) # This code is contributed by nikhilsainiofficial546 |
C#
// C# code for the above approach: using System; using System.Collections.Generic; // Structure for Node of Trie public class Node { // Links of string trie public Node[] links = new Node[26]; // Count of similar prefixes strings has public int cnt = 0; } public class Program { // Root node initialized static Node root = new Node(); // Insert function for inserting words in trie static void insert( string word) { // Initializing node variable Node node = root; // Iterating on given word for ( int i = 0; i < word.Length; i++) { // If node does not exist 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 static void remove( string word) { // Initializing node vaiable Node node = root; // Iterating on given word for ( int i = 0; i < word.Length; i++) { // Next node node = node.links[word[i] - 'a' ]; // Decrementing the counter node.cnt--; } } // Finding common prefix in all other strings static int query( string word) { // Count of answer int cnt = 0; // Initialization of node variable Node node = root; // Iterating on given word for ( int i = 0; i < word.Length; 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 static void findLCP(List< 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 Console.Write(query(A[i]) + " " ); // Inserting i'th string again insert(A[i]); } Console.WriteLine(); } // Driver program to test above functions public static void Main() { List< string > A1 = new List< string > { "abc" , "abb" , "aac" }; int N1 = 3; // Call for test case 1 findLCP(A1, N1); List< string > A2 = new List< string > { "abracadabra" , "bracadabra" , "racadabra" , "acadabra" , "cadabra" , "adabra" , "dabra" , "abra" , "bra" , "ra" , "a" }; int N2 = 11; // Call for test case 2 findLCP(A2, N2); } } // This code is contributed by Pushpesh Raj. |
Javascript
// JavaScript code for the above approach: // Structure for Node of Trie class Node { // Links of string trie constructor() { this .links = Array(26).fill( null ); // Count of similar prefixes // strings has this .cnt = 0; } } // Root node initialized const root = new Node(); // Insert function for inserting // words in trie function insert(word) { // Initializing node variable let node = root; // Iterating on given word for (let i = 0; i < word.length; i++) { // If node does not exists if (node.links[word.charCodeAt(i) - 97] === null ) { // Creating new node node.links[word.charCodeAt(i) - 97] = new Node(); } // Next node node = node.links[word.charCodeAt(i) - 97]; // Incrementing counter node.cnt++; } } // Remove function for removing // words in trie function remove(word) { // Initializing node variable let node = root; // Iterating on given word for (let i = 0; i < word.length; i++) { // Next node node = node.links[word.charCodeAt(i) - 97]; // Decrementing the counter node.cnt--; } } // Finding common prefix in all // other strings function query(word) { // Count of answer let cnt = 0; // Initialization of node variable let node = root; // Iterating on given word for (let i = 0; i < word.length; i++) { // If doesn't exist break; if (node.links[word.charCodeAt(i) - 97] === null ) break ; // Next node node = node.links[word.charCodeAt(i) - 97]; // 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 function findLCP(A, N) { // Inserting all strings in Trie for (let i = 0; i < N; i++) insert(A[i]); // Finding answer for ith string for (let i = 0; i < N; i++) { // Deleting current string from Trie remove(A[i]); // Printing answer for i'th string console.log(query(A[i]) + " " ); // Inserting i'th string again insert(A[i]); } console.log( "" ); } // Driver program to test above functions const A1 = [ "abc" , "abb" , "aac" ]; const N1 = 3; // Call for test case 1 findLCP(A1, N1); const A2 = [ "abracadabra" , "bracadabra" , "racadabra" , "acadabra" , "cadabra" , "adabra" , "dabra" , "abra" , "bra" , "ra" , "a" , ]; const N2 = 11; // Call for test case 2 findLCP(A2, N2); |
2 2 1 4 3 2 1 0 1 0 4 3 2 1
Time Complexity: O(N*K2), where N is the number of strings and K is the maximum length of the strings.
Auxiliary Space: O(N*K)
Related Articles:
Contact Us