Can this problem be solved without SAM ?
Difference between en1 and en2, changed 132 character(s)
[problem link](https://www.spoj.com/problems/AE5A2/).↵

I found a SAM solution on [luogu](https://www.luogu.com.cn/problem/solution/SP4311), but it is too hard for me to learn SAM, I wonder if there exists a solution without SAM.↵

<spoiler summary="Problem statement">↵
We called string $t$ a Quasi-template of string $s$, if and only if $t$ is a substring of $s$ and there exists at least one pair of integers $(l,r)$ satisfying:↵

- $1 \le l \le r \le |s|$ (string is $1$- indexd).↵
- $s[1 \ldots l-1]$ is a suffix of $t$ and $s[r+1 \ldots |s|]$ is a prefix of $t$.↵
- $\forall i \in [l,r]$, there exists at least one pair of integers $(L,R)$ satisfying $1 \le L \le i \le R \le n$ and $s[L \ldots R] = t$. ↵

Given string $s$, you need to find:↵

- How many distinct Quasi-template does $s$ have ?↵
- The shortest Quasi-template of $s$. If there are multiple, output the smallest one.↵

$1 \le |s| \le 2 \cdot 10^5$.↵
 ↵
</spoiler>↵

---↵

**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)