Аврора Интенсив Респ день1

int lmax = 0, pcnt = 0;

void Manaker(string s)
{
    pcnt = 0, lmax = 0;
    int n = s.size();
    vector<int> d1(n), d2(n);
    int l = -1, r = -1;
    for (int i = 0; i < n; i++)
    {
        int k = (i > r ? 1 : min(d1[l + r - i], r - i + 1));
        while (i - k >= 0 && i + k < n && s[i - k] == s[i + k]) k++;
        d1[i] = k;
        if (i + k - 1 > r)
        {
            l = i - k + 1;
            r = i + k - 1;
        }
    }
    //l1=d1[i]+d1[i]-1
    d2[0] = 0;
    l = -1; r = -1;
    for (int i = 1; i < n; i++)
    {
        int k = (i > r ? 0 : min(d2[l + r - i + 1], r - i + 1));
        while (i + k < n && i - k - 1 >= 0 && s[i + k] == s[i - k - 1]) k++;
        d2[i] = k;
        if (i + k - 1 > r)
        {
            l = i - k;
            r = i + k - 1;
        }
    }
    //l2=d2[i]*2
    for (int i = 0; i < n; i++)
    {
        lmax = max(max(d1[i] * 2 - 1, d2[i] * 2), lmax);
        pcnt += d1[i] + d2[i];
    }
}

vector<int> getHashV(vector<vector<int>>& hash, int i, int l)
{
    vector<int> v;
    int cst = 0;
    while (l)
    {
        if (l & 1)
        {
            v.push_back(hash[cst][i]);
            i += (1 << cst);
        }
        cst++;
        l >>= 1;
    }
    return v;
}

void SuffArr(string s)
{
    pcnt = 0;
    lmax = 0;
    int n = s.size();
    string s2 = s;
    reverse(s2.begin(), s2.end());
    s = s + "#" + s2;
    long long mult = max((size_t)256, s.size());
    int st = 0;
    while ((1 << st) < s.size()) st++;
    s.resize(1 << st, '#');
    vector<vector<int>> hash(st + 1);
    hash[0].resize(s.size());
    for (int i = 0; i < s.size(); i++)
        hash[0][i] = s[i];
    for (int k = 1; k <= st; k++)
    {
        vector<pair<long long, int>> prehash(s.size() - (1 << k) + 1);
        for (int i = 0; i < prehash.size(); i++)
        {
            prehash[i] = { mult * hash[k - 1][i] + hash[k - 1][i + (1 << (k - 1))], i };
        }
        hash[k].resize(prehash.size());
        sort(prehash.begin(), prehash.end());
        int num = -1;
        long long lhash = -1;
        for (auto& a : prehash)
        {
            if (a.first != lhash)
                num++;
            hash[k][a.second] = num;
            lhash = a.first;
        }
    }
    vector<int> d1(n), d2(n);
    for (int i = 0; i < n; i++)
    {
        int l = 0, r = i;
        while (r > l)
        {
            int m = (l + r + 1) / 2;
            int i1 = i - m;
            int i2 = n + (n - i) - m;
            vector<int> v1 = getHashV(hash, i1, m), v2 = getHashV(hash, i2, m);
            if (equal(v1.begin(), v1.end(), v2.begin(), v2.end()))
                l = m;
            else
                r = m - 1;
        }
        d1[i] = r + 1;

        if (i == 0)
        {
            d2[i] = 0;
            continue;
        }
        l = 0, r = i;
        while (r > l)
        {
            int m = (l + r + 1) / 2;
            int i1 = i - m;
            int i2 = n + (n - i) + 1 - m;
            vector<int> v1 = getHashV(hash, i1, m), v2 = getHashV(hash, i2, m);
            if (equal(v1.begin(), v1.end(), v2.begin(), v2.end()))
                l = m;
            else
                r = m - 1;
        }
        d2[i] = r;
        }
    for (int i = 0; i < n; i++)
    {
        lmax = max(max(d1[i] * 2 - 1, d2[i] * 2), lmax);
        pcnt += d1[i] + d2[i];
    }
}

int main() {
#ifdef DEBUG
    freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
#endif
    string s;
    cin >> s;
    Manaker(s);
    cout << "palindrome count: " << pcnt << "; longest palindrome length: " << lmax << endl;
    SuffArr(s);
    cout << "palindrome count: " << pcnt << "; longest palindrome length: " << lmax << endl;
    return 0;
}