Can this problem be solved without SAM ?

Revision en2, by little_dog, 2024-03-23 11:57:32

problem link.

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!

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English little_dog 2024-03-23 11:57:32 132
en1 English little_dog 2024-03-22 09:32:31 983 Initial revision (published)