Đếm Xâu Đối Xứng

Buổi 56 — Suffix Array & LCP
Points
85
AC Rate
0.0%
Time limit
3.0 s
Memory limit
256M
Group
string
Submissions
Đề bài

Cho xâu $S$ gồm các chữ cái in thường. Hãy đếm số lượng xâu con đối xứng (palindrome) phân biệt (không rỗng) của $S$.

Hai xâu con coi là giống nhau nếu nội dung giống nhau.

Sử dụng mảng hậu tố và mảng LCP kết hợp với xâu $S$ và xâu đảo ngược $S^R$ để giải quyết.

Dữ liệu vào

Một dòng chứa xâu $S$ ($1 \le |S| \le 10^5$) chỉ gồm các chữ cái in thường.

Dữ liệu ra

Một số nguyên duy nhất là số lượng xâu con đối xứng phân biệt.

Ví dụ
Input Output
banana 7
Giới hạn
  • $1 \le |S| \le 10^5$
  • $S$ chỉ gồm chữ cái in thường.
Draft saved