0

How to find the sum of length of Longest Common Prefixes of all pairs of substrings of a given string. For eg answer for string "aba" is 8. |s|<=1e5.

Mr. Hilton
  • 33
  • 5
  • LCP: http://stackoverflow.com/questions/8578349/longest-common-prefix-for-n-string and the rest would seem trivial. Finding all substrings. Although what do you mean by "sum" the LCP? Multiply its length by how many times it appears? I guess that means it matters that there are two equally long longest common prefixes. – Kenny Ostrom Mar 21 '17 at 12:59
  • sum is adding the length of LCP. – Mr. Hilton Mar 21 '17 at 18:55
  • why is it 8 for "aba"? – starikoff Mar 21 '17 at 21:25
  • LCP is 2. It's a tie between "ab" and "ba". Four different substrings have one of those prefixes. I've never been good with trie's -- can you put a reference count on the trie nodes? That would really make all the twists in this question trivial changes to longest common prefix (which is already answered). – Kenny Ostrom Mar 21 '17 at 22:17

0 Answers0