P7457 - String Distance

内存限制：128 MB 时间限制：4 S

题面：传统评测方式：文本比较上传者：

提交：7 通过：5

提交提交记录统计 Web Board

For two strings S and T, you can do the following operation for 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 defifined

as the minimum number of operations to make S and T equal.

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

In each query, you will be given two integers li and ri (1 ≤ li ≤ ri ≤ n), you need to fifind the distance

between the continous substring A[li ..ri] and the whole string B.

The fifirst line of the input contains a single integer T (1 ≤ T ≤ 10), the number of test cases.

For each case, the fifirst line of the input contains a string A consists of n (1 ≤ n ≤ 100 000) lower-case

English letters.

The second line of the input contains a string B consists of m (1 ≤ m ≤ 20) lower-case English letters.

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

Then in the following q lines, there are two integers li , ri (1 ≤ li ≤ ri ≤ n) in each line, denoting a query.

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

1
qaqaqwqaqaq
qaqwqaq
3
1 7
2 8
3 9

4
2
0

2020多校2

7457: String Distance