P6640 [BJOI2020] Seal

Note: The NOI 2020 Beijing team selection was canceled due to force majeure, and the provincial team was selected based on the previous year's CSP-S Round 2 results. Because there were ties, an additional test was held to decide the final Team A list. This problem is the additional test problem.

Given two strings $s, t$ that contain only lowercase letters $a, b$, there are $q$ queries. In each query, ask for the length of the longest common substring of $s[l \dots r]$ and $t$.

The input has $q+3$ lines. The first line contains a string $s$. The second line contains a string $t$. The third line contains an integer $q$. The next $q$ lines each contain two integers $l_i, r_i(1\le l_i \le r_i \le |s|)$, representing one query.

Output has $q$ lines. The $i$-th line is the length of the longest common substring of $s[l_i \dots r_i]$ and $t$.

| Test Point ID | $\vert s\vert , \vert t\vert \le $ | $q\le$ | | :-----------: | :--------------------------------: | :------------: | | $1$ | $50$ | $50$ | | $2,3$ | $2\times 10^3$ | $2\times 10^3$ | | $4,5$ | $2\times 10^5$ | $10$ | | $6\sim 10$ | $2\times 10^5$ | $2\times 10^5$ | Translated by ChatGPT 5