CF1817F Entangled Substrings

量子纠缠是指两个粒子以某种方式相互关联，无论它们在空间中相距多远。 给定一个字符串 $s$。如果一对非空子串 $(a, b)$ 满足存在一个（可能为空的）连接字符串 $c$，使得： - $s$ 中每一次出现 $a$ 都紧接着出现 $cb$； - $s$ 中每一次出现 $b$ 都紧接着出现在 $ac$ 之后。 换句话说，$a$ 和 $b$ 只会作为 $acb$ 的子串出现在 $s$ 中。请计算 $s$ 的所有纠缠子串对的总数。 如果字符串 $a$ 可以通过从字符串 $b$ 的开头删除若干（可能为零或全部）字符，并从结尾删除若干（可能为零或全部）字符得到，则称 $a$ 是 $b$ 的子串。

输入仅一行，包含一个仅由小写英文字母组成的字符串 $s$（$1 \leq |s| \leq 10^5$），即需要统计纠缠子串对的字符串。

输出一个整数，表示 $s$ 的纠缠子串对的总数。

在第一个样例中，唯一的纠缠对子串对是 (ab, ba)。对于这对子串，连接字符串 $c$ 为空，因为它们只作为整个字符串 abba 的子串出现，ab 和 ba 之间没有其他字符。 在第二个样例中，没有纠缠对子串对。 在第三个样例中，纠缠对子串对有 (a, b)、(b, c)、(a, c)、(a, bc) 和 (ab, c)。对于大多数对子，连接字符串 $c$ 为空，只有对于 (a, c) 这一对，连接字符串 $c$ 是 b，因为 a 和 c 只作为字符串 abc 的子串出现。 由 ChatGPT 4.1 翻译