[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!↵
↵
↵
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!↵
↵
