Time limit: 1.0s , Memory limit: 256M , Points: 15 (partial)
Bạn được cho hai xâu kí tự và
(chỉ gồm các chữ cái in hoa).
Nhiệm vụ của bạn hãy đếm số lượng xâu con của
thỏa mãn đồng thời hai điều kiện:
là dãy con của
- Nghịch đảo của
là dãy con của
Xâu được gọi là xâu con của
nếu
được tạo ra bằng cách không xóa hoặc xóa một số phần tử ở hai đầu của
.
Xâu được gọi là dãy con của
nếu
được tạo ra bằng cách không xóa hoặc xóa một số phần tử của
mà không thay đổi thứ tự của các phần tử còn lại.
Input
- Dòng đầu tiên chứa số nguyên
là số bộ test (
).
- Mỗi bộ test gồm 2 dòng chứa hai xâu
và
(
).
Output
- Với mỗi bộ test, in ra trên một dòng là số lượng xâu
thỏa mãn.
Samples
Input 1
2
ABABA
AB
ZZ
Z
Output 1
6
3
Scoring
- Subtask
(50% số điểm):
- Subtask
(50% số điểm):
Notes
Ở bộ test thứ nhất, có 6 cách chọn xâu con thỏa mãn: ABABA, ABABA, ABABA, ABABA, ABABA và ABABA
Comments