#38. 垃圾题

内存限制:128 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Shu_Yu_Mo

题目描述

给定两个字符串 S,T ,有 q 次询问,每次给定 l,r,s,t ,表示询问 T[s:t] 第一次在 S[l:r] 中出现的位置,如果无解输出 0

字符串下标从 1 开始

输入格式

第一行一个字符串 S

第二行一个字符串 T

接下来一个正整数 q

接下来 q 行每行四个正整数 l,r,s,t

输出格式

q 行,表示询问的答案

样例

abcbababab
ababcbabab
5
1 9 7 9
3 10 8 10
1 10 1 2
5 7 2 3
1 5 3 6
5
4
1
6
1

数据范围与提示

100\% : |S|=|T|\le 10^5,q\le 10^5

对全部数据,保证 O(n^2) 理论可过。