Lời giải: Xử lý offline. Gọi xâu ~S~ và ~T~ là xâu ~s~ và ~t~ sau khi đã xử lí hết các query, ta tính ~A(S, T)~, sau đó trả lời các query theo trình tự ngược lại.

Với ~0 \leq i \leq |T| - 1~, đặt ~PF_i = \max j | T[0..j-1] = T[i-j+1..i]~ Với ~0 \leq i \leq |S| - 1~, đặt ~KMP_m(i) = \max j | j <= m, T[0..j - 1] = S[i - j + 1..i]~.

• Nhận xét 1: ~PF~ tạo thành cấu trúc cây, với cha của ~i~ là ~p(i) = PF_i - 1~.

• Nhận xét 2:

  ~KMP_{m - 1}(i) = PF_{KMP_{m}(i) - 1}~ nếu ~KMP_{m}(i) = m~

  ~KMP_{m - 1}(i) = KMP_{m}(i)~ nếu ~KMP_{m}(i) < m~.

Ta maintain một mảng ~c_j~ là số số ~i~ sao cho ~0 \leq i < n~ và ~KMP_m(i) = j~ và biến ~S~ là ~A(S[0..n - 1], T[0..m - 1])~.

• Nhận xét 3: ~A(S[0..n - 1], T[0..m - 1])~ = ~\sum_{j=1}^m c_j*sum_{j - 1}~, trong đó ~sum_{j - 1} = j - 1 + p(j - 1) + p(p(j - 1)) + .. + 0~ (lấy tổng các tổ tiên của ~j - 1~ trong cây từ nhận xét 1).

Ta xử lý 2 query như sau:

• Query 1. bỏ một chữ cái khỏi đuôi ~s~, tức ~n = n - 1~. Ta dùng binary lifting, xuất phát từ ~KMP_{|T|}(n - 1)~ để tìm ~KMP_m(n - 1)~. Ta update ~c_{KMP_m(n - 1)} = c_{KMP_m(n - 1)} - 1~, và update ~S~ tương ứng.

• Query 2. bỏ một chữ cái khỏi đuôi ~t~, tức ~m = m - 1~. Ta update ~c_{PF_{m - 1}} += c_m~ và ~c_m = 0~, và update S tương ứng.

Việc đảo ngược query cũng chỉ để update gọn gàng hơn, hoàn toàn có thể làm xuôi.

Code C++: https://pastebin.com/qxf9QGHq