emoji's blog

A string related question
By emoji, history, 8 years ago, In English

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.

  • Vote: I like it
  • -10
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Are you sure it can be done in time complexity better than O(N2)?

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    This question is on hackerrank with the same constraints.

    → Reply
»
8 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Use suffix automaton. After build, recalc cnt[i] for all node (cnt[i] = count ways to last node). for all i

→ Reply