String Hashing (phần 2) - Bộ đề bài - LQDOJ: Le Quy Don Online Judge

#	Bài tập	Điểm	Thời gian:	Giới hạn bộ nhớ
1	Xâu đối xứng	100 (p)	1.0s	256M
2	Tạo palindrome	150 (p)	1.0s	256M
3	Hai thao tác trên chuỗi	200 (p)	1.0s	256M

1. Xâu đối xứng

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Một xâu được gọi là đối xứng nếu đọc từ trái qua phải và đọc từ phải qua trái đều giống nhau.

Ví dụ xâu "aba", "abba" là xâu đối xứng; còn xâu "abc", "abca" thì không.

Bạn được cho \(N\) xâu, như vậy sẽ có \(N × N\) cặp xâu. Bạn hãy đếm xem trong \(N×N\) cặp xâu này, có bao nhiêu cặp mà khi nối xâu thứ hai vào sau xâu thứ nhất sẽ cho ra một xâu đối xứng.

Input

Dòng đầu ghi một số \(N\).
\(N\) dòng sau mỗi dòng mô tả một xâu, bắt đầu là độ dài của xâu, sau đó là một dấu cách và tiếp theo là nội dung của xâu. (Xâu chỉ gồm các chữ cái latin thường và có độ dài nguyên dương)

Dữ liệu vào luôn đảm bảo tổng độ dài các xâu không quá 1000000.

Output

Ghi ra một số duy nhất là số cặp xâu tìm được.

Example

Test 1

Input

3
1 a
2 ab
2 ba

Output

2. Tạo palindrome

Điểm: 150 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Cho một xâu \(s\). Cần thêm ít nhất bao nhiêu ký tự vào cuối xâu \(s\) để tạo thành một xâu đối xứng? In ra xâu đối xứng đó.

Input

Dòng đầu tiên chứa một số nguyên dương \(t\), số truy vấn bạn phải trả lời \((1 \leq t \leq 100)\).
\(t\) dòng tiếp theo, mỗi dòng chứa một xâu \(s\).
Tổng độ dài các xâu \(s\) không vượt quá \(5 \times 10^5\).

Output

Với mỗi truy vấn, in ra một dòng là xâu đối xứng tạo thành.

Example

Test 1

Input

4
aaaa
abba
amanaplanacanal
xyz

Output

aaaa
abba
amanaplanacanalpanama
xyzyx

3. Hai thao tác trên chuỗi

Điểm: 200 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

John có một chuỗi \(S\). John được yêu cầu thực hiện hai thao tác sau theo thứ tự trên \(S\):

Chọn một vị trí của \(S\), và thay thế bằng bất kỳ ký tự nào John muốn.
Dịch chuyển chuỗi \(S\), nghĩa là, John có thể chọn một vị trí \(k\) và dịch chuỗi \(S\) theo vòng tròn sao cho \(k\) trở thành vị trí bắt đầu của chuỗi mới.

John muốn sau khi thực hiện hai phép toán trên, kết quả thu được là một chuỗi cho trước. Bạn hãy giúp John tính số cách biến đổi từ chuỗi \(S\) thành một chuỗi \(T\) cho trước.

Input

Dữ liệu bao gồm hai chuỗi \(S\) và \(T\) trên một dòng. Mỗi chuỗi bao gồm nhiều nhất 100000 ký tự và chỉ gồm các ký tự in hoa.
Đảm bảo rằng \(S\) và \(T\) có cùng số ký tự.

Output

Một số duy nhất là số cách biến đổi từ chuỗi \(S\) thành chuỗi \(T\).

Example

Test 1

Input

AHYANGYI YANGYIAH

Output

Note

John có thể thay thế chữ "A" đầu tiên bằng "A", hoặc "H" bằng 'H", v.v... nghĩa là có thể thay thế một chữ bằng chính chữ đó.
Sau đó, chỉ có một cách để dịch chuyển chuỗi.

Test 2

Input

VSUMSU MSUMSU

Output

Note

John cần thay thế chữ "V" đầu tiên bằng "M".
Sau đó, John có hai cách để dịch chuyển chuỗi (\(k=1\) hoặc \(k=4\)).