Problem
Tom Sawyer và Huckleberry Finn cùng nhau đọc to một mẩu báo. Nhưng tình cờ là Tom Sawyer bắt đầu đọc từ ký tự thứ i, và Huckleberry Finn từ ký tự thứ j.
Họ có thể đọc được bao nhiêu chữ cái trước khi phát hiện ra chúng bắt đầu từ những chỗ khác nhau hoặc cho đến khi cả hai cùng đọc đến cuối?
Đầu vào:
Dòng đầu tiên chứa chuỗi S (1 <= |S| <= 10
5), bao gồm các chữ cái Latinh viết thường - một dòng chữ từ một mẩu báo.
Dòng tiếp theo ghi số tự nhiên q - số lượng yêu cầu.
Q dòng tiếp theo chứa hai số tự nhiên i và j mỗi số - vị trí mà từ đó Tom Sawyer và Huckleberry Finn bắt đầu đọc tương ứng.
Đầu ra:
In q dòng, mỗi dòng chứa một số nguyên - số ký tự khớp khi đọc các chuỗi con bắt đầu bằng ký tự thứ i và thứ j.
Ví dụ:
| Đầu vào |
Đầu ra |
abacaba
4
15
3 5
4 2
26 |
3
1
0
2 |