Fast Travel Text Editor (Codeforces 1860E)
Tags: Others, 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: 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: For each query, print the minimum number of actions required to move the cursor from position $$$f$$$ to position $$$t$$$.


Sample Inputs:
codecode
3
1 7
3 5
3 6

abcdefghij
3
1 9
9 1
5 5

aaaaaaaaaaaa
4
10 8
3 7
6 1
11 11

Sample Outputs:
3
2
2

8
8
0

1
1
1
0

Solution (Python):
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def g(u, v):
    return 26 * u + v

def bfs(s):
    dist = [inf] * n
    ok = [0] * m
    (q1, q2) = (list(s), [])
    for i in s:
        dist[i] = 0
    di = 0
    while q1:
        for i in q1:
            if i > 0 and dist[i - 1] == inf:
                dist[i - 1] = di + 1
                q2.append(i - 1)
            if i < n - 1 and dist[i + 1] == inf:
                dist[i + 1] = di + 1
                q2.append(i + 1)
            if not ok[u[i]]:
                ok[u[i]] = 1
                for j in z[u[i]]:
                    if dist[j] == inf:
                        dist[j] = di + 1
                        q2.append(j)
        (q1, q2, di) = (q2, [], di + 1)
    return dist
s = list(input().rstrip())
s = [i - 97 for i in s]
n = len(s)
u = [g(s[i], s[i + 1]) for i in range(n - 1)]
v = [-1] * (26 * 26)
m = 0
for i in u:
    if v[i] == -1:
        v[i] = m
        m += 1
u = [v[i] for i in u]
n -= 1
z = [[] for _ in range(m)]
for i in range(n):
    z[u[i]].append(i)
q = int(input())
ans = []
(f, t) = ([0] * q, [0] * q)
inf = pow(10, 9) + 1
ans = [inf] * q
q0 = []
for i in range(q):
    (f0, t0) = map(int, input().split())
    (f0, t0) = (f0 - 1, t0 - 1)
    if f0 == t0:
        ans[i] = 0
    elif u[f0] == u[t0]:
        ans[i] = 1
    else:
        q0.append(i)
        (f[i], t[i], ans[i]) = (f0, t0, abs(f0 - t0))
for i in range(m):
    dist = bfs(z[i])
    for j in q0:
        ans[j] = min(ans[j], dist[f[j]] + dist[t[j]] + 1)
sys.stdout.write('\n'.join(map(str, ans)))

Solution (Python):
import sys
input = sys.stdin.readline
INF = 10 ** 9
K = 26 * 26
A = [ord(char) - ord('a') for char in input().rstrip()]
n = len(A)
G = [[] for _ in range(K)]
for i in range(1, n):
    v = A[i - 1] * 26 + A[i]
    G[v].append(i)
m = int(input())
queries = [tuple(map(int, input().split())) for _ in range(m)]
res = [abs(f - t) for (f, t) in queries]
for v in range(K):
    if not G[v]:
        continue
    vis = [False] * K
    vis[v] = 0
    dist = [INF] * n
    q = list(G[v])
    for j in G[v]:
        dist[j] = 0
    for idx in range(n - 1):
        i = q[idx]
        if i < n - 1 and dist[i + 1] == INF:
            dist[i + 1] = dist[i] + 1
            q.append(i + 1)
        if i > 1 and dist[i - 1] == INF:
            dist[i - 1] = dist[i] + 1
            q.append(i - 1)
        v = A[i - 1] * 26 + A[i]
        if not vis[v]:
            vis[v] = True
            for j in G[v]:
                if dist[j] == INF:
                    dist[j] = dist[i] + 1
                    q.append(j)
    for (i, (f, t)) in enumerate(queries):
        res[i] = min(res[i], dist[f] + dist[t] + 1)
print('\n'.join(map(str, res)))

Solution (Python):
import sys
from collections import deque
from array import array
input = lambda : sys.stdin.readline().rstrip()

def chr2idx(c):
    return ord(c) - 97
s = input()
s = [chr2idx(a) * 26 + chr2idx(b) for (a, b) in zip(s, s[1:])]
N = len(s)
P = 26 ** 2
connected = [[] for _ in range(P)]
for i in range(N):
    connected[s[i]] += [i]
dist = [array('i', [N + 1] * N) for _ in range(P)]
for p in range(P):
    portal_visited = [False] * P
    portal_visited[p] = True
    visited = [False] * N
    q = deque([])
    for i in connected[p]:
        visited[i] = True
        dist[p][i] = 0
        q += [i]
    while q:
        i = q.popleft()
        if i - 1 >= 0 and (not visited[i - 1]):
            visited[i - 1] = True
            dist[p][i - 1] = dist[p][i] + 1
            q.append(i - 1)
        if i + 1 < N and (not visited[i + 1]):
            visited[i + 1] = True
            dist[p][i + 1] = dist[p][i] + 1
            q.append(i + 1)
        if not portal_visited[s[i]]:
            portal_visited[s[i]] = True
            for j in connected[s[i]]:
                if not visited[j]:
                    visited[j] = True
                    dist[p][j] = dist[p][i] + 1
                    q.append(j)
m = int(input())
for _ in range(m):
    (f, t) = map(lambda x: int(x) - 1, input().split())
    ans = abs(f - t)
    for p in range(P):
        ans = min(ans, dist[p][f] + dist[p][t] + 1)
    print(ans)