TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P3221
  • 题目
  • P322101序列问题
    限制 : 时间限制 : 25000 MS   空间限制 : 565536 KB
    问题描述

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

    输入格式

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

    输出格式

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

    样例输入

    6 6
    000111
    111100
    3
    1 1
    1 2
    4 2

    样例输出

    1
    0
    3

    提示

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

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

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

    所有对齐位都是相同的。


    来源  感谢nodgd命题,感谢ShadowIterator放题