Блог пользователя 156302

Question about a problem using Suffix Array

Автор 156302, история, 6 лет назад, По-английски

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

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Anybody? :(

→ Ответить
»
6 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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.

→ Ответить