Problem
トム・ソーヤーとハックルベリー・フィンは一緒に新聞の切り抜きを読み上げました。しかし、たまたま、トム・ソーヤーは i 番目の文字から読み始め、ハックルベリー・フィンは j 番目の文字から読み始めました。
違う場所から始めたことに気付くまで、または両方とも最後まで読むまでに、何通の手紙を読むことができますか?
入力:
最初の行には、小文字のラテン文字で構成される文字列 S (1 <= |S| <= 10
5) が含まれています - 新聞の切り抜きからの碑文です。
次の行には、自然数 q - リクエストの数が含まれています。
次の q 行には、それぞれ 2 つの自然数 i と j が含まれています。これは、トム ソーヤーとハックルベリー フィンがそれぞれ読み始める位置です。
出力:
q 行を出力します。各行には 1 つの整数 (i 番目と j 番目の文字で始まる部分文字列を読み取るときに一致する文字数) が含まれている必要があります。
例:
<本体>
| 入力 |
出力 |
アバカバ
4
15
3 5
4 2
26 |
3
1
0
2 |