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!