156302's blog

By 156302, history, 5 weeks ago, In English,

Hi, I'm having trouble understanding the solution of the following problem http://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?

 
 
 
 

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Anybody? :(

»
4 weeks 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.