بلند خواندن
Problem
تام سایر و هاکلبری فین یک بریده روزنامه را با صدای بلند خواندند. اما اینطور شد که تام سایر شروع به خواندن از شخصیت i-ام و هاکلبری فین از j-ام کردند.
چند حرف را می توانند بخوانند قبل از اینکه بفهمند از جاهای مختلف شروع شده اند، یا تا زمانی که هر دو تا آخر بخوانند؟
ورودی:
خط اول شامل رشته S (1 <= |S| <= 10
5)، متشکل از حروف کوچک لاتین - کتیبه ای از بریده روزنامه.
خط بعدی حاوی یک عدد طبیعی q است - تعداد درخواست‌ها.
سطرهای q بعدی هر کدام شامل دو عدد طبیعی i و j هستند - به ترتیب موقعیت هایی که تام سایر و هاکلبری فین از آنها شروع به خواندن می کنند.
خروجی:
خطوط q را چاپ کنید، که هر کدام باید دارای یک عدد صحیح باشد - تعداد کاراکترهایی که هنگام خواندن زیررشته‌هایی که با کاراکترهای i و j-ام شروع می‌شوند مطابقت دارند.
مثال:
<بدن>
| ورودی |
خروجی |
abacaba
4
15
3 5
4 2
26 |
3
1
0
2 |