class Solution {
    std::string expend(const std::string& s) {
        std::string res = "@#";
        for (int i = 0; i < s.size(); i++)
            res += s[i], res += '#';
        res += '%';
        return res;
    }

    std::vector<int> Manacher(const std::string& s) {
        auto t = expend(s);
        // std::cout<<t<<"\n";
        std::vector<int> p(t.size(), 1);
        for (int i = 1, r = 0, c = 0; i < t.size() - 1; i++) {
            p[i] = (r > i ? std::min(p[2 * c - i], r - i) : 1);
            while (t[i - p[i]] == t[i + p[i]])
                ++p[i];
            if (i + p[i] > r) {
                r = i + p[i];
                c = i;
            }
        }
        return p;
    }

public:
    int countSubstrings(string s) {
        auto p = Manacher(s);
        int ans = 0;
        for (int k : p)
            ans += k / 2;
        return ans;
    }
};