Just calculating the suffix array solves the problem if you do it with the LCP array as well. You don't need to 'use' the suffix array so to speak.
On 19 August 2012 21:45, pankajsingh <psingh...@gmail.com> wrote: > Is there any O(n) solution this question...I Cleared all the testcases but > my solution is not O(n) and...I think there should be some O(n) > solution..by seeing the constraint to this question..I tried to think for > Kmp in this ..but didnt work....and suffix array method will have more > complexity..any suggestion > > "" > > For two strings A and B, we define the similarity of the strings to be the > length of the longest prefix common to both strings. For example, the > similarity of strings "abc" and "abd" is 2, while the similarity of strings > "aaa" and "aaab" is 3. > > Calculate the sum of similarities of a string S with each of it's suffixes. > > *Input:* > The first line contains the number of test cases T. Each of the next T > lines contains a string each. > > *Output:* > Output T lines containing the answer for the corresponding test case. > > *Constraints:* > 1 <= T <= 10 > The length of each string is at most 100000 and contains only lower case > characters. > > ""-- > Pankaj Singh > B.Tech in Computer Science and Engineering - lllrd year > IIT Roorkee, India > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algogeeks@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
