i have solved some easy problems on suffix array,i think this problemcan be solved using suffix array,but i am not getting any approach that can suffice the time limit.
Please Help by giving idea on how to solve the problem(preferably by using suffix array)...
Thanks in advance :)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | jiangly | 3810 |
| 2 | Benq | 3676 |
| 3 | Kevin114514 | 3655 |
| 4 | maroonrk | 3463 |
| 5 | strapple | 3390 |
| 6 | Um_nik | 3387 |
| 7 | tourist | 3384 |
| 8 | heuristica | 3322 |
| 9 | turmax | 3319 |
| 10 | jiangbowen | 3291 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 155 |
| 2 | nik_exists | 150 |
| 2 | maspy | 150 |
| 4 | Um_nik | 143 |
| 5 | AmShZ | 141 |
| 6 | Errichto | 139 |
| 7 | adamant | 137 |
| 8 | maroonrk | 134 |
| 9 | BledDest | 132 |
| 10 | qwexd | 129 |
I think you can solve it by KMP(knuth morris pratt) or Z-function algorithm.
If we solve it by KMP it's O(|s|^2) — for each prefix and suffix we find the number of times it occurs in O(|s|).
No, it can be solved in O(|S|).
First, we just build prefix-function array for S, let's call it pi. If we have pi[i] = x, we not only have prefix of length x ending at position i, but also prefixes of length pi[x - 1], pi[pi[x - 1] - 1] and so on. The number of "good" prefixes for each value of the prefix function can be calculated using DP.
UPD. Fixed a typo.
I have solved the question using zFunction... My submission — http://codeforces.me/contest/432/submission/8510013
Along with computing suffix array you can compute LCP array (lcp[i] is Longest Common Prefix for adjacent suffixes i and i + 1). Now you can use sparse tables or RangeMinimumQuery to determine how many suffixes have equal prefix of length k.
Such an overkilling... There is much easier solution with suffix automaton! 8946328