Or a suffix tree would work. Pre process it to answer Lowest common ancestor queries.
On 19 August 2012 21:51, Carl Barton <odysseus.ulys...@gmail.com> wrote: > 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.
