I found a SAM solution on luogu, but it is too hard for me to learn SAM, I wonder if there exists a solution without SAM.
Problem statement
UPD: I solved it with Suffix Array, DSU, KMP, Fenwick tree and Segment tree merging in $$$\mathcal O(n \log n)$$$, Yay!
what is SAM ?
Suffix Automaton
Looks similar to poi05_sza
The problem you gave is with an additional constraint: $$$l = 1,r = n$$$ must hold. Then the vaild string $$$t$$$ is a border of string $$$s$$$ and it could be solved with suffix array :(
Oh i missed that, sry
Auto comment: topic has been updated by little_dog (previous revision, new revision, compare).