CF1817F.Entangled Substrings

Quantum entanglement is when two particles link together in a certain way no matter how far apart they are in space.

You are given a string $s$. A pair of its non-empty substrings $(a, b)$ is called entangled if there is a (possibly empty) link string $c$ such that:

• Every occurrence of $a$ in $s$ is immediately followed by $cb$;
• Every occurrence of $b$ in $s$ is immediately preceded by $ac$.

In other words, $a$ and $b$ occur in $s$ only as substrings of $acb$. Compute the total number of entangled pairs of substrings of $s$.

A string $a$ is a substring of a string $b$ if $a$ can be obtained from $b$ by the deletion of several (possibly zero or all) characters from the beginning and several (possibly zero or all) characters from the end.

量子纠缠是指两个粒子以某种方式相互关联，无论它们在空间中相距多远。

给定一个字符串 $s$。其一对非空子串 $(a, b)$ 被称为纠缠的（entangled），当且仅当存在一个（可能为空的）连接字符串 $c$，使得：

• $s$ 中 $a$ 的每一次出现都紧随其后为 $cb$；
• $s$ 中 $b$ 的每一次出现都紧邻其前为 $ac$。

换言之，$a$ 和 $b$ 在 $s$ 中仅作为 $acb$ 的子串出现。请计算 $s$ 的纠缠子串对的总数。

若字符串 $a$ 可通过从字符串 $b$ 的开头删除若干（可能为零或全部）字符、并从结尾删除若干（可能为零或全部）字符而得到，则称 $a$ 是 $b$ 的子串。

The first and only line contains a string $s$ of lowercase English letters ($1 \leq |s| \leq 10^5$) — the string for which you should count pairs of entangled substrings.

第一行且唯一一行包含一个由小写英文字母组成的字符串 $s$（$1 \leq |s| \leq 10^5$），你需要统计该字符串中“纠缠子串”对的数量。

Output a single integer, the number of entangled pairs of substrings of $s$.

输出一个整数，表示字符串 $s$ 中纠缠子串对的数量。

In the first example, the only entangled pair is (ab,ba). For this pair, the corresponding link string $c$ is empty, as they only occur as substrings of the whole string abba, which doesn't have any characters between ab and ba.

In the second example, there are no entangled pairs.

In the third example, the entangled pairs are (a,b), (b,c), (a,c), (a,bc), and (ab,c). For most pairs, the corresponding link string $c$ is empty, except for the pair (a,c), for which the link string $c$ is b, as a and c only occur as substrings of the string abc.

在第一个例子中，唯一的纠缠对是 (ab, ba)。对于该对，对应的连接字符串 $c$ 为空，因为 ab 和 ba 仅作为整个字符串 abba 的子串出现，而 ab 与 ba 之间没有字符。

在第二个例子中，不存在纠缠对。

在第三个例子中，纠缠对为 (a, b)、(b, c)、(a, c)、(a, bc) 和 (ab, c)。对于大多数对，对应的连接字符串 $c$ 为空；但对 (a, c)，其连接字符串 $c$ 为 b，因为 a 和 c 仅作为字符串 abc 的子串出现。