TouchStone
  Please Login
Login Sign Up
 Homepage  Problem Set  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P3221
  • Problem
  • P322101序列问题
    Limits : Time Limit : 25000 MS   Memory Limit : 565536 KB
    Description

    给出两个长度为n的01序列A、B,有Q次询问,每次询问当把A的第i位和B的第j位对齐时,A,B公共部分有多少对对齐且相同的数。

    Input Format

    第一行,两个整数N,M。
    第二行,一个长度为N的字符串,只包含'0'和'1'两种字符,代表A序列。
    第三行,一个长度为M的字符串,只包含'0'和'1'两种字符,代表B序列。
    第四行,一个整数Q。
    接下来Q行,每行两个整数i,j。

    Output Format

    输出Q行,每行表示每次询问的答案。

    Sample Input

    6 6
    000111
    111100
    3
    1 1
    1 2
    4 2

    Sample Output

    1
    0
    3

    Hint

    数据范围:
    1<=N,M<=105
    1<=Q<=106

    样例解释:
    第二次询问
     000111
    111100

    对齐的位中没有相同的。
    第三次询问
    000111
       111100

    所有对齐位都是相同的。


    Source  感谢nodgd命题,感谢ShadowIterator放题