P8835 [ChuanZhi Cup #3 Finals] Substring

disangan233 likes strings, so disangan333 wants you to find some strings that disangan233 likes.

In ChuanZhi’s development class, you are expected to develop a document processing software. Given $T$ queries, each query provides $2$ strings $a, b$ of lengths $n, m$ consisting only of English letters. Find the number of occurrences of $a$ in $b$, where uppercase and lowercase of the same letter are not distinguished. Note that $a$ is a contiguous subsequence (substring) of $b$. For all testdata, $T \leq 100$, $\sum n \leq \sum m \leq 10^3$. The strings consist only of uppercase or lowercase English letters.

The input has a total of $3T + 1$ lines. Line $1$ contains $1$ positive integer $T$. Then there are $T$ groups of input, each group has $3$ lines. Line $1$ contains $2$ positive integers $n, m$. Line $2$ contains a string $a$ of length $n$. Line $3$ contains a string $b$ of length $m$.

Output $T$ lines. Line $i$ outputs $1$ integer, indicating the answer to query $i$.

For the first group of input, it appears $3$ times, namely `[abc]abcabca`, `abc[abc]abca`, `abcabc[abc]a`. For the second group of input, it appears $9$ times, namely `[Aa]AaaAaAa`, `A[aA]aaAaAa`, `Aa[Aa]aAaAa`, `AaA[aa]AaAa`, `AaAa[aA]aAa`, `AaAaa[Aa]Aa`, `AaAaaA[aA]a`, `AaAaaA[aA]a`, `AaAaaAa[Aa]`. Translated by ChatGPT 5