20612번 - String Distance 다국어

For two strings $S$ and $T$, you can do the following operation an arbitrary number of times: Select a string $S$ or $T$, insert or delete a character at any position. The distance between two strings $S$ and $T$ is defined as the minimum number of operations to make $S$ and $T$ equal.

You will be given two strings $A[1..n]$ and $B[1..m]$, and also $q$ queries.

In each query, you will be given two integers $l_i$ and $r_i$ ($1 \leq l_i \leq r_i \leq n$). You need to find the distance between the continuous substring $A[l_i..r_i]$ and the whole string $B$.

The first line contains a single integer $T$ ($1 \leq T \leq 10$), the number of test cases. For each test case:

The first line contains a string $A$ which consists of $n$ ($1 \leq n \leq 100\,000$) lower-case English letters.

The second line contains a string $B$ which consists of $m$ ($1 \leq m \leq 20$) lower-case English letters.

The third line contains a single integer $q$ ($1 \leq q \leq 100\,000$) denoting the number of queries.

Each of the following $q$ lines contains two integers $l_i$ and $r_i$ ($1 \leq l_i \leq r_i \leq n$) describing a query.

For each query, print a single line containing an integer denoting the answer.