156302's blog

Question about a problem using Suffix Array

By 156302, history, 6 years ago, In English

Hi, I'm having trouble understanding the solution of the following problem http://mirror.codeforces.com/contest/802/problem/I using Suffix Array, that is, the first solution in Editorial. Can someone more familiar with Suffix Array explain the solution to me?

  • Vote: I like it
  • 0
  • Vote: I do not like it

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

Anybody? :(

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

cnt(s, p) = k for some p. Notice that
0 + 1 + ... + (k-1) = (k^2 — k) / 2 = "that sum" for some p.
You can find "that sum" for all p by using data structure described in editorial.

So to find sum(k^2) you need to multiply it by 2 and add sum(k), which is a number of substrings of s.

→ Reply