Want to know about lcp array and its generation using binary search

#1

Given a array of N strings, find the longest common prefix among all strings present in the array.

Input:
The first line of the input contains an integer T which denotes the number of test cases to follow. Each test case contains an integer N. Next line has space separated N strings.

Output:
Print the longest common prefix as a string in the given array. If no such prefix exists print “-1”(without quotes).

Constraints:
1 <= T <= 103
1 <= N <= 103
1 <= |S| <= 103

Example:
Input:
2
4
geeksforgeeks geeks geek geezer
3
apple ape april

Output:
gee
ap

#2

Heyy Utkarsh !!!
I am going to tell 2 ways of this finding LCP array .

  1. Binary Seach --> Select smallest string among all ,let’s say it’s legnth be L and then apply binary search on it with lower limit as 0 and uppper limit as L-1 . And check for mid wheather it is possible to have mid(mid=(si+ei)/2) as our LCP , if it is then you just need to append the characers from 0 to mid in our answer string and then jump into right part i.e. mid+1 to ei , Otherwise jump into left part (0 to mid-1) . Hope you get the idea using Binary Seach .

  2. Trie --> Insert all the words one by one in the trie. After inserting , perform a walk on the trie.
    In this walk, go deeper until we find a node having more than 1 children(branching occurs) or 0 children (one of the string gets exhausted).
    This is because the characters (nodes in trie) which are present in the longest common prefix must be the single child of its parent, i.e- there should not be a branching in any of these nodes.

If you talk about efficiency then Trie will be much efficient than Binary Search as time taken by them are as follows ->>

  1. NMlogM
    2.NM ,where M is length of shortest string and N is number of strings in the input .
    I Hope this gives you some idea about computing LCP Array .
1 Like