310348: CF1817F. Entangled Substrings
Description
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.
InputThe 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.
OutputOutput a single integer, the number of entangled pairs of substrings of $s$.
ExamplesInputabbaOutput
1Input
abacabaOutput
0Input
abcabcabcabcOutput
5Input
adamantOutput
82Note
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.
Input
题意翻译
给定字符串 $s$。 $s$ 的非空子串对 $(a, b)$ 合法，当且仅当存在可空字符串 $c$，使得每次 $a$ 在 $s$ 中出现，后面都紧跟着 $cb$；且每次 $b$ 在 $s$ 中出现，前面都紧跟着 $ac$。即 $a, b$ 只以 $acb$ 的形式在 $s$ 中出现。 求 $s$ 的合法非空子串对数量。 $1\leq |s|\leq 10 ^ 5$。 翻译贡献者：[Alex_Wei](https://www.luogu.com.cn/user/123294)。Output
量子纠缠是指两个粒子以一定的方式连接在一起，无论它们在空间中相隔多远。
给你一个字符串 s。如果 s 的两个非空子字符串 (a, b) 存在一个（可能为空）的连接字符串 c，使得：
- s 中 a 的每次出现都紧跟着 cb；
- s 中 b 的每次出现都紧随着 ac。
则称 (a, b) 为纠缠的。换句话说，a 和 b 在 s 中只作为 acb 的子字符串出现。计算 s 的纠缠子字符串对的总数。
输入数据格式：
第一行包含一个由小写英文字母组成的字符串 s（1 ≤ |s| ≤ 10^5）—— 你应该计算其纠缠子字符串对的字符串。
输出数据格式：
输出一个整数，即 s 的纠缠子字符串对的数量。
示例：
输入：abba
输出：1
输入：abacaba
输出：0
输入：abcabcabcabc
输出：5
输入：adamant
输出：82
注意：
在第一个示例中，唯一的纠缠对是 (ab,ba)。对于这对，相应的连接字符串 c 为空，因为它们只作为整个字符串 abba 的子字符串出现，而 abba 在 ab 和 ba 之间没有任何字符。
在第二个示例中，没有纠缠对。
在第三个示例中，纠缠对是 (a,b), (b,c), (a,c), (a,bc), 和 (ab,c)。对于大多数对，相应的连接字符串 c 为空，除了对 (a,c)，其连接字符串 c 为 b，因为 a 和 c 只作为字符串 abc 的子字符串出现。题目大意： 量子纠缠是指两个粒子以一定的方式连接在一起，无论它们在空间中相隔多远。 给你一个字符串 s。如果 s 的两个非空子字符串 (a, b) 存在一个（可能为空）的连接字符串 c，使得： - s 中 a 的每次出现都紧跟着 cb； - s 中 b 的每次出现都紧随着 ac。 则称 (a, b) 为纠缠的。换句话说，a 和 b 在 s 中只作为 acb 的子字符串出现。计算 s 的纠缠子字符串对的总数。 输入数据格式： 第一行包含一个由小写英文字母组成的字符串 s（1 ≤ |s| ≤ 10^5）—— 你应该计算其纠缠子字符串对的字符串。 输出数据格式： 输出一个整数，即 s 的纠缠子字符串对的数量。 示例： 输入：abba 输出：1 输入：abacaba 输出：0 输入：abcabcabcabc 输出：5 输入：adamant 输出：82 注意： 在第一个示例中，唯一的纠缠对是 (ab,ba)。对于这对，相应的连接字符串 c 为空，因为它们只作为整个字符串 abba 的子字符串出现，而 abba 在 ab 和 ba 之间没有任何字符。 在第二个示例中，没有纠缠对。 在第三个示例中，纠缠对是 (a,b), (b,c), (a,c), (a,bc), 和 (ab,c)。对于大多数对，相应的连接字符串 c 为空，除了对 (a,c)，其连接字符串 c 为 b，因为 a 和 c 只作为字符串 abc 的子字符串出现。