题解

字符串的半前缀即前缀删除一个子串后得到的字符串，可以用$s[1…i]+s[j…k]$表示。

问题即给定一个长度为$n(n \leq 10^6)$的字符串，求其半前缀的个数。

\textbf{对于这种本质不同的字符串计数问题，通常都是将某个串在它第一次或最后一次出现时统计。}

本题中，如果将每个字符串在第一次出现的前缀中（即尽可能缩短用到的前缀长度），那么看起来就不太能做。但是如果将每一个串在最后一次出现的前缀中统计，就会非常简单：对于一个串，假设它可以表示为 $s[1…i]+s[j…k]$ 和 $s[1…i+a]+s[j+a…k]$，那么有 $s_{i+1}=s_j$。并且，如果它不能表示为 $s[1…i+1]+s[j+1…k]$ 的形式，必然也不能表示成 $s[1…i+a]+s[j+a…k],a>0$，而且有 $s_{i+1}≠s_j$。这也就是说，对于一个串 $t=s[1…i]+s[j…k]$，它是最后一次出现在某个前缀中，当且仅当 $s_{i+1}≠s_j$。所以我们要做的事情实际上就是对于每个后缀 $s[i+1…n]$，求出它包含的本质不同子串个数，减掉以 $s_{i+1}$ 开头的不同子串个数即可。这个操作可以用 $SAM$ 简单维护。