# Solution Bài 2 TS
Subtask 1:
- Giới hạn: s ≤ 500
- Hướng giải: Duyệt qua tất cả các chuỗi con có thể có trong chuỗi s và kiểm tra xem chuỗi con đó có đối xứng hay không. Nếu đối xứng, tăng biến đếm lên 1.

Subtask 2:
- Giới hạn: s ≤ 1000
- Hướng giải: Sử dụng phương pháp DP để xác định các chuỗi con đối xứng. Sử dụng một ma trận isPalindrome[n][n] để lưu trữ thông tin về tính đối xứng của các chuỗi con. Duyệt qua tất cả các độ dài chuỗi con từ 1 đến n, sau đó duyệt qua tất cả các vị trí i trong chuỗi s. Kiểm tra xem chuỗi con từ vị trí i đến i + len - 1 có đối xứng hay không và cập nhật giá trị trong ma trận isPalindrome. Tăng biến đếm lên 1 cho mỗi chuỗi con đối xứng tìm thấy.

Subtask Full:
- Giới hạn: s ≤ 1e5
- Hướng giải: Sử dụng phương pháp Manacher để tìm số lượng chuỗi đối xứng trong chuỗi s. Xây dựng chuỗi p bằng cách thêm ký tự đặc biệt vào giữa mỗi ký tự trong chuỗi s và ở đầu và cuối chuỗi. Sử dụng một mảng a để lưu trữ thông tin về độ dài chuỗi đối xứng tại mỗi vị trí trong chuỗi p. Duyệt qua từng vị trí trong chuỗi p và tính giá trị tương ứng của mảng a bằng phương pháp Manacher. Cuối cùng, tính tổng độ dài chuỗi đối xứng từ các giá trị trong mảng a và trả về kết quả.

Đây là đoạn code tham khảo:

#include<bits/stdc++.h>
#define Nhin_lai_cuoc_doi() ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
using namespace std;
const int maxsub1 = 500;
const int maxsub2 = 1000;
const int full = 1e5 + 33;
string pre(string s) {
    string p = "#";
    p.reserve(2 * s.length() + 1);
    for (int i = 0; i < s.length(); i++) {
        p += s[i];
        p += '#';
    }
    return p;
}
bool palin(string s) {
    long long int l = 0, r = s.length() - 1;
    while (l < r) {
        if (s[l] != s[r])
            return false;
        l++;
        r--;
    }
    return true;
}
long long sub1(string s) {
    long long res = 0, n = s.length();
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            string substring = s.substr(i, j - i + 1);
            if (palin(substring))
                res++;
        }
    }
    return res;
}

long long sub2(string s) {
    long long res = 0, n = s.length();
    vector<vector<bool>> ispalin(n, vector<bool>(n, false));
    for (int i = 0; i < n; i++) {
        ispalin[i][i] = true; 
        res++;                     
    }
    for (int len = 2; len <= n; len++) {
        for (int i = 0; i < n - len + 1; i++) {
            int j = i + len - 1;
            if (s[i] == s[j]) {
                if (len == 2 || ispalin[i + 1][j - 1]) {
                    ispalin[i][j] = true;
                    res++;
                }
            }
        }
    }
    return res;
}

long long subfull(string s) {
    string p = pre(s);
    long long n = p.length();
    vector<long long> a(n, 0);
    long long c = 0, rr = 0, m = 0;
    for (int i = 0; i < n; i++) {
        if (i < rr) {
            int j = 2 * c - i;
            a[i] = min(rr - i, a[j]);
        }
        long long l = i - (a[i] + 1), r = i + (a[i] + 1);
        while (l >= 0 && r < n && p[l] == p[r]) {
            a[i]++;
            l--;
            r++;
        }
        if (i + a[i] > rr) {
            c = i;
            rr = i + a[i];
        }
        m = max(m, a[i]);
    }
    long long res = 0;
    for (int i = 0; i < a.size(); i++) {
        int len = a[i];
        res += (len + 1) / 2;
    }
    return res;
}
int main() {
	Nhin_lai_cuoc_doi();
    freopen("DOIXUNG.INP", "r", stdin);
    freopen("DOIXUNG.OUT", "w", stdout);
    string s;
    getline(cin, s);
    long long res;
    if (s.length() <= maxsub1) res = sub1(s);
    else if (s.length() <= maxsub2) res = sub2(s);
    else res = subfull(s);
    printf("%lld\n", res);
    return 0;
}