Fast Travel Text Editor
Contest: Educational Codeforces Round 153 (Rated for Div. 2)
Difficulty rating: 2400
Tags: data structures, dfs and similar, graphs, shortest paths

You are given a string $$$s$$$, consisting of lowercase Latin letters.

There's a cursor, initially placed between two adjacent letters of the string. The cursor can't be placed before the first or after the last letter.

In one move, you can perform one of three actions:

- move a cursor one position to the left (if that doesn't place it before the first letter);
- move a cursor one position to the right (if that doesn't place it after the last letter);
- let $$$x$$$ be the letter immediately to the left of the cursor, and $$$y$$$ be the letter immediately to the right of the cursor. Choose any pair of adjacent letters in the string such that the left of them is $$$x$$$ and the right of them is $$$y$$$, and move the cursor to the position between these two letters.

You are asked $$$m$$$ queries. In each query, you are given two integers $$$f$$$ and $$$t$$$, which correspond to two valid positions of the cursor in the string. In response to the query, you have to calculate the minimum number of operations required to move the cursor from position $$$f$$$ to position $$$t$$$.

Input format:
The first line contains a string $$$s$$$ ($$$2 \le |s| \le 5 \cdot 10^4$$$), consisting of lowercase Latin letters.

The second line contains a single integer $$$m$$$ ($$$1 \le m \le 5 \cdot 10^4$$$) — the number of queries.

The $$$i$$$-th of the next $$$m$$$ lines contains two integers $$$f$$$ and $$$t$$$ ($$$1 \le f, t \le |s| - 1$$$) — the initial and the target positions of the cursor in the $$$i$$$-th query. Position $$$x$$$ means that the cursor is between the $$$x$$$-th and the $$$(x+1)$$$-st letters of the string ($$$1$$$-indexed).

Output format:
For each query, print the minimum number of actions required to move the cursor from position $$$f$$$ to position $$$t$$$.

Constraints:
Time limit: 5.0 s
Memory limit: 512.0 MB

Example input:
codecode
3
1 7
3 5
3 6

Example output:
3
2
2

Example input:
abcdefghij
3
1 9
9 1
5 5

Example output:
8
8
0

Editorial:
Let's start with the easiest slow solution.
We can basically treat the problem as a graph one. There are $$$n-1$$$ vertices and the operations represent edges: from $$$i$$$ to $$$i+1$$$, from $$$i+1$$$ to $$$i$$$ and from $$$i$$$ to $$$j$$$ if $$$s_i = s_j$$$ and $$$s_{i+1} = s_{j+1}$$$.
Then, for a query, we can run any algorithm that finds the shortest path. For example, BFS. That will be $$$n^2$$$ per query in the worst case, because the third type of actions produces a lot of edges.
Let's try to optimize the third action. If you look at the edges between all positions linked by the third action, they just form cliques. So the distance between every pair of vertices should be equal to $$$1$$$. Instead of having a lot of edges, we can add a dummy vertex that simulates this behavior. For example, add a directed edge from each vertex in the clique to the dummy vertex of weight $$$1$$$ and a directed edge back of weight $$$0$$$. Now, you can travel from one vertex to another in the clique in $$$1$$$, but only use $$$O(n)$$$ edges in total.
Thus, the BFS for each query will be linear. Well, a couple of things are wrong with that statement... First, not a regular BFS, of course, but a 0-1 BFS now, since there are edges of weight $$$0$$$. Second, there are also some dummy vertices. How many of them? Each clique is induced by all positions that have the same letters to the left and to the right of them. So, there are $$$|A|^2$$$ options, where $$$|A| = 26$$$, and $$$n + |A|^2$$$ vertices in total.
To optimize further, let's investigate the structure of the path. There are trivial paths: they just go left or right without using the third action. We can initialize the answer with them.
Otherwise, a path uses the jump to the dummy node at least once. Let that node be $$$s$$$. So, the path looks like $$$f \rightarrow s$$$, then $$$s \rightarrow t$$$. Let's use the fact that there are not that many candidates for $$$s$$$. We can iterate over $$$s$$$ and update the answer with each of them. If the optimal path goes through any of them, we will find it.
And calculating $$$f \rightarrow s$$$ or $$$s \rightarrow t$$$ is way easier. First, $$$f \rightarrow s$$$ is the same as $$$s \rightarrow f$$$ in a transposed graph (all edges are reversed). Second, we can calculate the shortest path from $$$s$$$ to all vertices with a single 0-1 BFS.
Thus, we get a solution in $$$O(|A|^2 \cdot (n + |A|^2 + q))$$$. We can either run $$$|A|^2$$$ BFS's before reading the queries and save the results, using $$$O(|A|^2 \cdot n)$$$ memory. Alternatively, we can read the queries, then run each BFS and update the answer with its results immediately for $$$O(n + |A|^2)$$$ memory. The second option will generally also be faster by a constant factor, since there are fewer cache misses.