Entangled Substrings
Contest: Codeforces Round 869 (Div. 1)
Difficulty rating: 3500
Tags: string suffix structures, strings

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.

Input format:
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.

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

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
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.

Example input:
abba

Example output:
1

Example input:
abacaba

Example output:
0

Editorial:
Suffix automaton approach. For every substring $$$a$$$ of $$$s$$$ we can define the longest string $$$\hat{a}$$$ such that $$$a$$$ only occurs in $$$s$$$ as a specific substring of $$$\hat{a}$$$. To find $$$\hat{a}$$$, we find the longest strings $$$x$$$ and $$$y$$$ such that the occurrences of $$$a$$$ are always preceded by $$$x$$$ and always succeeded by $$$y$$$. Then, we can say that $$$\hat{a} = x a y$$$.
If you're familiar with suffix structures you would recognize that in this terms, $$$xa$$$ is the longest string that belongs to the same state of the suffix automaton of $$$s$$$ as $$$a$$$. Knowing that, how would we find $$$\hat{a} = x a y$$$? When we add a new character at the end of a substring, we make a transition in the suffix automaton via this character.
Generally, if the state of the string $$$xa$$$ has transitions via two different characters, it would mean that the string $$$y$$$ is empty, as it means that different strings may succeed the occurrences of $$$xa$$$. Also, if the state is terminal, it would mean that the last occurrence of $$$xa$$$ is at the suffix of $$$s$$$ and it can not be succeeded by any non-empty string. If the state is not terminal, and its only transition is by a character $$$c$$$, it means that the string $$$xa$$$ is always succeeded by $$$c$$$.
The facts above mean that to find $$$xay$$$, we may start with the state of the suffix automaton that corresponds to the string $$$a$$$, and then, while the state is non-terminal, and it only has a single out-going transition, we move to a next state via this transition. In the end, $$$xay$$$ would be the longest string of the state we ended up in.
Now back to the problem. Note that if a string $$$a$$$ only occurs in $$$s$$$ as a substring of another string $$$t$$$, it means that $$$\hat{a} = \hat{t}$$$. In terms of the strings $$$a$$$, $$$b$$$ and $$$c$$$ from the statement it means that $$$\hat{a} = \hat{b} = \widehat{acb}$$$.
Assume that we grouped together the states of the suffix automaton that end up in the same state if you follow unique out-going transitions from them until you get into a state with two possible transitions, or a terminal state. Each group corresponds to a unique largest string such that any string that belongs to any state from the group only occurs in $$$s$$$ as a specific substring of the largest string.
Note that for strings that belong to the same state of the suffix automaton, they also have the same string $$$y$$$. The length $$$|y|$$$ determines the unique position in which all the strings from the state occur in the largest string as set of nested suffixes. So, for the largest string $$$t$$$, their right position of occurrences will be $$$|t|-|y|$$$, and their lengths form the contiguous segment $$$[len(link(q)) + 1, len(q)]$$$. Thus, the whole problem reduces for each group of states to the following:
We have a bunch of triplets $$$(l_1, l_2, r)$$$. Each triple denotes a set of segments $$$[l_1, r], [l_1 + 1, r], \dots, [l_2, r]$$$. You need to count the number of non-overlapping pairs of segments. This can be done in $$$O(n \log n)$$$ with the help of segment tree.
Suffix array approach. There is an alternative solution using suffix arrays (suggested by Dario).
Let $$$a_0, \dots, a_{n-1}$$$ be the suffix array and $$$b_0, \dots, b_{n-2}$$$ be the longest common prefix of adjacent elements of the suffix array.
1. We say that $$$[l, r]$$$ is good for length $$$len$$$ if the positions $$$a[l, r]$$$ are exactly the occurrences of a sub-string of length $$$len$$$. This is equivalent to $$$b_{l-1}, b_r < len$$$ and $$$b_i \geq len$$$ for all $$$l \leq i < r$$$.
2. There are at most $$$O(n)$$$ good intervals (an interval is good if it is good for any length). Indeed they are a subset of the sub-trees of the Cartesian tree of the array $$$b$$$.
3. Now we iterate over the good intervals. Let $$$[l, r]$$$ be a good intervals for the lengths $$$[u, v]$$$. Consider a translation $$$t$$$ and check if by adding $$$t$$$ to all elements $$$a_l, a_{l+1}, .., a_r$$$ one gets a good interval. This can be checked in $$$O(1)$$$. This check can be done from $$$t=u$$$ to $$$t=v$$$ and one can stop as soon as a bad $$$t$$$ is found. If t is a good translation; then we can count in $$$O(1)$$$ the corresponding good pairs of sub-strings $$$A, B$$$. And this concludes the problem.
4. It remains to perform quickly step 3. Given two good intervals $$$I, J$$$ we say that $$$J$$$ follows $$$I$$$ if $$$a[J]$$$ coincides with the array one obtains adding $$$1$$$ to all elements of $$$a[I]$$$. The "following" relationship creates a family of chains on the good intervals.
5. One performs step 3 independently on the various chains.