Xâu hoàn hảo

Xem PDF
Tác giả:
lethienquan28052006
Dạng bài
Điểm: 300 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Sau đây là một câu chuyện có thật do Quandeptrai bịa ra:

Quandeptrai là một chàng trai từ nhỏ đã rất đẹp trai, hào hoa, phong độ, rất nhiều cô gái theo đuổi. Một hôm, trong lúc đi chơi với bạn gái của mình(Thảo xinhgai) , cô bạn gái của Quandeptrai nhờ cậu giúp cô giải một bài tập về xâu kí tự. Khổ nỗi, Quandeptrai không giỏi môn tin lắm, cho nên cậu đã nhờ các anh em coder giải giúp cậu bài tập này:

Xâu hoàn hảo là xâu có độ dài lớn hơn hoặc bằng 2, trong đó kí tự đầu và kí tự cuối của xâu bằng nhau. Cho một xâu \(S\) có độ dài \(N\), đếm số lượng xâu hoàn hảo trong xâu \(S\).

Input

  • Dòng đầu tiên là số nguyên dương \(N\) – độ dài của xâu \(S\) \((n \leq 10^6)\)

  • Dòng thứ 2 là xâu S chỉ gồm các kí tự chữ cái latinh in thường.

Output

  • Ghi ra một số nguyên duy nhất là số lượng xâu hoàn hảo trong xâu \(S\).

Scoring

  • Subtask \(1\) (\(30\%\) số điểm): \(N\leq 10^3\)
  • Subtask \(2\) (\(70\%\) số điểm): \(N\leq 10^6\)

Example

Test 1

Input 
6
abcacb
Output 
3

Bình luận