Problem:


  MathJax.Hub.Config({ tex2jax: { inlineMath: [["$","$"], ["\\(","\\)"]], processEscapes: true }});

文字列 S と， m 個のクエリが与えられる．i 番目のクエリは二つの文字列 xi, yi で与えられる．

各クエリについて，文字列 S の部分文字列であり， xi で始まり yi で終わるものの中で，最長の長さを答えよ．

文字列 S について， |S| は S の長さを表す．また，文字列 T が文字列 S の部分文字列であるとは，ある整数 i が存在して， 1 ≤ j ≤ |T| に対して Tj = Si+j を満たすことを言う．ただし Tj は T の j 番目の文字を表す．

Input

入力は以下の形式で与えられる．

S
m
x1 y1
x2 y2
:
xm ym

 1 行目には，文字列 S が与えられる．

 2 行目には，クエリの個数 m が与えられる．

 3 行目からの m 行のうち i 行目には i 番目のクエリ文字列 xi, yi が空白区切りで与えられる．

Constraints

 1 ≤ |S| ≤ 2 &times; 105 

 1 ≤ m ≤ 105

 1 ≤ |xi|, |yi|

 $\sum^m_{i=1}$ (|xi| + |yi|) ≤ 2 &times; 105

 S 及び xi, yi は，半角の英小文字のみからなる．

Output

以下の形式で最大の部分文字列の長さを答えよ．

len1
len2
:
lenm

1 行目からの m 行のうち i 行目には， i 番目のクエリについて，条件を満たす最長の部分文字列の長さ leni を出力せよ．そのような部分文字列がない場合，0 を出力せよ．

Sample Input 1

abracadabra
5
ab a
a a
b c
ac ca
z z

Output for the Sample Input 1

11
11
4
3
0

文字列 S として，abracadabra が与えられる．

 "ab" で始まり "a" で終わる部分文字列は，"abra" や "abraca", "abracada", "abracadabra" の4 種類があるが，最長の部分文字列は "abracadabra" で，長さは 11 である．

 "a" で始まり "a" で終わる最長の部分文字列も同様に "abracadabra" で，長さは 11 である．

 "b" で始まり "c" で終わる最長の部分文字列は "brac" で，長さは 4 である．

 "ac" で始まり "ca" で終わる最長の部分文字列は "aca" で，長さは 3 である．

 "z" で始まり "z" で終わる部分文字列は存在しない．よって0 を出力する．

Sample Input 2

howistheprogress
4
ist prog
s ss
how is
the progress

Output for the Sample Input 2

9
12
5
11

Sample Input 3

icpcsummertraining
9
mm m
icpc summer
train ing
summer mm
i c
i i
g g
train i
summer er

Output for the Sample Input 3

2
10
8
0
4
16
1
6
6



Sample input:
abracadabra
5
ab a
a a
b c
ac ca
z z


Sample output:
11
11
4
3
0

Submission status: Wrong Answer

Solution code:
s = input()
m = int(input())
for i in range(m):
    x,y = map(str,input().split())
    ans = s.rfind(y) - s.find(x)
    if ans != 0:
        ans += 1
    if len(y) > 1:
        ans += len(y) - 1
    print(ans)

Submission status: Wrong Answer

Solution code:
s = input()
m = int(input())
for i in range(m):
    x,y = map(str,input().split())
    ans = s.rfind(y) - s.find(x)
    if x in s and y in s:
        ans += 1
    if len(y) > 1:
        ans += len(y) - 1
    if len(x) > ans:
        ans = 0
    print(ans)

Submission status: Wrong Answer

Solution code:
s = input()
m = int(input())
for i in range(m):
    x,y = map(str,input().split())
    ans = s.rfind(y) - s.find(x)
    if len(x) <= len(s) and len(y) <= len(s):
        if x in s and y in s:
            ans += 1
        if len(y) > 1:
            ans += len(y) - 1
        if len(x) > ans:
            ans = 0
    else:
        ans = 0
    print(ans)

Submission status: Wrong Answer

Solution code:
s=input()
for _ in range(int(input())):
    a,b=input().split()
    if s.rfind(b)-s.find(a):
        if s.find(a)+len(a)+len(b)>s.rfind(b):print(s.rfind(b)-s.find(a)+2)
        else:print(s.rfind(b)-s.find(a)+1)
    else:print(0)

Submission status: Wrong Answer

Solution code:
s=input()
for _ in range(int(input())):
    a,b=input().split()
    if s.rfind(b)-s.find(a):
        c=len(b)
        if s.find(a)+len(a)+c>s.rfind(b):print(s.rfind(b)-s.find(a)+c)
        else:print(s.rfind(b)-s.find(a)+c)
    else:print(0)

Submission status: Time Limit Exceeded

Solution code:
s=input()
for _ in range(int(input())):
    a,b=input().split()
    c = len(b)
    if s.rfind(b)-s.find(a)<0 or s.find(a)+len(a)-c>s.rfind(b) or a not in s or b not in s:print(0)
    else:print(s.rfind(b)-s.find(a)+c)

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys
readline = sys.stdin.readline
write = sys.stdout.write
def solve():
    base = 37; MOD = 10**9 + 9
    S = readline().strip()
    L = len(S)
    H = [0]*(L+1)
    v = 0
    ca = ord('a')
    for i in range(L):
        H[i+1] = v = (v * base + (ord(S[i]) - ca)) % MOD
    M = int(readline())
    Q = []
    s = defaultdict(set)
    for i in range(M):
        x, y = readline().split()
        v0 = 0
        for c in x:
            v0 = (v0 * base + (ord(c) - ca)) % MOD
        s[len(x)].add(v0)
        v1 = 0
        for c in y:
            v1 = (v1 * base + (ord(c) - ca)) % MOD
        s[len(y)].add(v1)
        Q.append((len(x), v0, len(y), v1))
    fvs = {}; lvs = {}
    for l, vs in s.items():
        p = pow(base, l, MOD)
        fs = {}; ls = {}
        for i in range(L-l+1):
            v = (H[i+l] - H[i] * p) % MOD
            if v not in fs:
                fs[v] = i
            ls[v] = i
        fv = {}; lv = {}
        for v in vs:
            fv[v] = fs.get(v, L+1)
            lv[v] = ls.get(v, -1)
        fvs[l] = fv
        lvs[l] = lv
    for lx, x, ly, y in Q:
        p0 = fvs[lx][x]
        p1 = lvs[ly][y]
        if p0 <= p1 and p0+lx <= p1+ly:
            write("%d\n" % (p1+ly-p0))
        else:
            write("0\n")
solve()