EASYSTR - Một bài tập về xâu
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 0.3 giây
Giới hạn bộ nhớ: 256 megabyte
Đăng bởi: yurilover172

Cho 2 xâu a, b cùng độ dài n. Xét hàm f() sau:

f(S, i, j) = S(i + 1, j - 1) + rev(S(j, n)) + rev(S(1, i))

Trong đó:

- S(i, j) là xâu con từ i tới j của S. Quy ước nếu i > j thì S(i, j) là xâu rỗng.

- rev(S) là xâu đảo ngược của S.

Đếm số lượng cặp số (i,j) thỏa mãn 1 <= i < j <= n và f(a, i, j) = b.

Input:

- Dòng đầu tiên ghi xâu a.

- Dòng thứ hai ghi xâu b.

Output:

- Gồm một số nguyên duy nhất là kết quả bài toán.

Giới hạn:

- n <= 3.105.

- 2 xâu a, b gồm các ký tự in được (các ký tự có mã ASCII từ 32 tới 126).

Ví dụ

  • input
    aba
    aba
    output
    2

2 cặp số là (1, 2) và (2, 3).

Back to Top