Chętnie przyjmę wskazówkę / szkic / rozwiązanie :)

Googlamy prackę o ALCS https://www.sciencedirect.com/science/article/pii/S0166218X07002727 i przepisujemy krótki pseudokod, który w O(N*M) liczy dwuwymiarową tablicę ih[i][j]. Słuzy ona do tego, by liniowo odpowiadać na zapytanie: dla danych (i, j, k), znajdź LCS(A[0..i], B[j..k]). Sprowadza się to do policzenia wartości mniejszych/równych niż "j" w jakimś tam podprzedziale ih[i][...]. Zrozumienie tego pozwala użyć ekstra tablicy oraz sum prefiksowych, by dla danych (i, k) liniowo policzyć wynik dla wszystkich możliwych "j".

Podsumowując, robimy kwadratowy preprocessing, po czym dla zadanego prefiksu A i prefiksu B (które nazwijmy PA i PB), umiemy liniowo znaleźć wszystkie wyniki dla par (PA, sufiks(PB)).

=== Polecam w tym miejscu się zatrzymać i samemu skminić do końca, bo nie jest trudno. ===

.
.
.

Wczytujemy zapytania i odpowiadamy na nie offline. Robimy Divide&Conquer, na zmianę ciachając A i B na pół. Skupmy się na odpowiedzeniu na wszystkie zapytania, w których dany podprzedział A przechodzi przez środek słowa A. Nazwijmy dwie połówki słowa A jako AL i AR. Liczymy kwadratowo ALCS(reverse(AL), reverse(B)) oraz ALCS(AR, B), po czym odpowiadamy liniowo na każde zapytanie: pytamy te dwa alcs-y o odpowiednie prefiksy, dostajemy dwie tablice rozmiaru maksymalnie |B| i dają one nam wszystkie wyniki LCS(AL, prefiks B) i LCS(AR, sufiks B). Czyli udało nam się podzielić A na pół i możemy przeiterować się po tym, jaki prefiks podsłowa B będzie zmatchowany z lewą częścią podsłowa A.

Złożoność O(N^2 * log(N) + Q*N). Mój kod https://pastebin.com/iJB1TGmK

Dzięki za szczegółową odpowiedź!

Zauważę, że ciachanie obu na zmianę jest niepotrzebne. Można ciachać tylko jedno i taka sama złożoność.

https://codeforces.com/blog/entry/49769?#comment-337339

If you're reading this, you've been visited by the ghost of świstak past. Fast LCS implementations will come to you if you post "thank mr świstak" in this thread.

thanks mr świstak