Stelele Informaticii 2024 - Mirror Day 1 | Ľahký problém

Už žádné zbytečné příběhy
-- Vědecká komise, Den před zkouškou

Cerință

Fie $A, B$ două șiruri de caractere de lungime $N$, respectiv $M$. Să se determine cel mai lung subsir comun al celor două șiruri cu proprietatea că diferența dintre pozițiile oricăror două caractere consecutive din subsir este cel puțin $L$ și cel mult $U$.

Formal, se cere $k$ maxim pentru care există două șiruri de numere $1 \le a_1 < a_2 < \dots < a_k \le N$ și $1 \le b_1 < b_2 < \dots < b_k \le M$ astfel încât:

• Pentru orice $1 < j \le k$, $L \le a_j - a_{j-1}, b_j - b_{j-1} \le U$
• Pentru orice $1 \le j \le k$, $A_{a_j} = B_{b_j}$

Date de intrare

Pe prima linie a inputului se va găsi un număr $T$, numărul de testcaseuri. Urmează descrierea fiecărui testcase.

Pe prima linie a fiecărui testcase se vor găsi numerele $N, M, L, U$, reprezentând respectiv lungimea primului șir, lungimea celui de-al doilea șir, și limitele diferențelor dintre indici.

Pe a doua, respectiv a treia linie a fiecărui test se vor găsi stringurile $A$ și $B$.

Date de ieșire

Pentru fiecare testcase se va afișa un singur număr, pe linii separate --- lungimea maximă a unui subsir comun care respectă proprietățile din enunț.

Restricții și precizări

• $1 \le N, M \le 6\ 000$, și în particular că $S_N, S_M \le 6\ 000$, unde $S_N$ și $S_M$ reprezintă suma tuturor $N$-urilor din toate testcase-urile prezente într-un test, respectiv suma tuturor $M$-urilor din toate testcase-urile prezente într-un test;
• $1 \le L \le U \le max(N, M)$;
• $A$ și $B$ conțin doar litere mici ale alfabetului latin.

Exemplu

stdin

5
6 6 2 4
aaaaaa
aaaaaa
7 8 3 3
axxbxxc
axxxbxxc
7 8 3 4
axxbxxc
axxxbxxc
7 6 1 1
axabaaa
aaaaab
7 9 2 3
ggpxuam
gkxxkszhk

stdout

3
2
3
3
2

Explicație

Pentru primul exemplu, putem lua șirurile:

• $\underline{a}a\underline{a}a\underline{a}a$
• $a\underline{a}a\underline{a}a\underline{a}$

Pentru al patrulea exemplu, putem lua șirurile:

• $axab\underline{aaa}$
• $\underline{aaa}aab$