问题陈述
给定字符串$S$和$m$个查询。 第$i$个查询由两个字符串$x_i,y_i$给出。
对于每个查询,在字符串$S$的子字符串中,找出以$x_i$开头、以$y_i$结尾的子字符串,并回答其最长长度。
关于那条$S$, $|S|$ 表示 $S 的长度。 此外,字符串 $T$ $S如果整数 $i$ 使得 $1 \le j \le |对于 T|$,满足 $T_j = S_{i+j}$。这里,$T_j$ 表示 $T$ 的第 $j 个字符。
输入
输入格式如下。
$S$
$m$
$x_1$ $y_1$
$x_2$ $y_2$
:
:
$x_m$ $y_m$
- 第一行给出字符串$S$。
- 第二行标注了库里$m$的数量。
- 在第3行的$m$行中,第$i$行为第$i条查询字符串$x_i,y_i$留出空格。
约束
- $1 \le |S| \le 2 \乘以10^5 $
- $1 \le m \le 10^5$
- $1 \le |x_i|,|y_i|$
- $\sum_{i=1}^m (|x_i|+|y_i|) \le 2 \times 10^5$
- $S$ 和 $x_i,y_i$ 仅由小写半宽字母组成。
输出
回答以下格式中子串的最大长度。
$len_1$
$len_2$
:
:
$len_m$
对于第一行$m$的行$i$,输出满足第$i$查询eri条件的子字符串长度$len_i$。 如果不存在这样的子串,则输出0。
样本输入 1
abracadabra 5 ab a a a b c ac ca z z
样本输入 1 的输出
11 11 4 3 0
随着弦$S$,阿布拉卡达布拉被给予。
- "ab“从”a“副弦结尾是,”abra“是的”abraca","abracada","abracadabra共有四种类型,但末尾的子串是”abracadabra“长度是11。
- "a“从”a"以...结束的子字符串也是如此"abracadabra“长度是11。
- "b“从”c"以...结束的子字符串是"brac”,长度为4。
- "ac“从”ca"以...结束的子字符串是"aca”,长度为3。
- "z“从”z不存在以"结尾的子串,因此输出0。
示例输入 2
howistheprogress 4 ist prog s ss how is the progress
样本输入 2 的输出
9 12 5 11
示例输入 3
icpcsummertraining 9 mm m icpc summer train ing summer mm i c i i g g train i summer er
样本输入 3 的输出
2 10 8 0 4 16 1 6 6