← 返回题目列表

AtCoder · icpc2014summer_day4_f

F. 最长的匹配

中文机器翻译题面 查看原题

问题陈述

给定字符串$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