CVPDROME - Đếm xâu
Giới hạn- Thời gian: 2.0s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Một xâu S có độ dài n gồm các kí tự x1x2…xn được gọi là xâu đối xứng nếu nó thỏa mãn xi=xn-i+1 với mọi i=1…n. Xâu s được gọi là CVPdrome nếu ta đảo lại trật tự các kí tự thì thu được một xâu đối xứng. Cho xâu s gồm n kí tự.
Yêu cầu
:Tính số xâu con (gồm các kí tự liên tiếp của s) là CVPdrome.
Input:
Dòng 1: Số nguyên dương N (1<=N<=3*10^5) là độ dài xâu s.
Dòng 2: Xâu s, các kí tự trong s là các chữ cái latin thường hoặc hoa (‘A’->’Z’ hoặc ‘a’->’z’).
Ouput:
Một dòng duy nhất ghi số nguyên kết quả.
Ví dụ:
Input:
3
aaa
Output:
6
Input:
3
aAA
Output:
5
Giải thích các xâu (1,1),(1,3),(2,2),(2,3),(3,3) là các CVPdrome. Xâu aAA không là xâu đối xứng nhưng ta có thể viết lại nó thành AaA là một xâu đối xứng.
- Người up: c_hunter
- Nguồn bài: NEERC 2012