How to find all occurences of each substring in the given string.Please give me some suggestions
How to find all occurences of each substring in the given string.Please give me some suggestions
| # | User | Rating |
|---|---|---|
| 1 | Benq | 3676 |
| 2 | Kevin114514 | 3659 |
| 3 | jiangly | 3640 |
| 4 | turmax | 3450 |
| 5 | tourist | 3382 |
| 6 | strapple | 3360 |
| 7 | Um_nik | 3354 |
| 8 | squareOf105 | 3348 |
| 9 | maroonrk | 3312 |
| 10 | idontwannadothis…e | 3191 |
| # | User | Contrib. |
|---|---|---|
| 1 | Qingyu | 158 |
| 2 | nik_exists | 151 |
| 3 | maspy | 149 |
| 4 | AmShZ | 144 |
| 5 | Um_nik | 143 |
| 6 | Errichto | 139 |
| 7 | adamant | 136 |
| 8 | BledDest | 133 |
| 9 | maroonrk | 132 |
| 10 | Proof_by_QED | 131 |
you can easily make that in O(N*N*N) time using Brute force. Then using hashes it can be reduced to O(N*N). You cAn make that in O(N*N) using KMP.
Z-Function.
If I understood the problem correctly, then using suffix array + lcp should give performance between O(N) and
depending on chosen algorithm for searching suffix array.
actually i asked to have the count for every substring in the string
Yes, there is no way of doing that in O(N) as there can be ~ N2 different substrings. I was thinking of problem where I had to count number of different substrings.