palindromic_length.cpp

#include <bits/stdc++.h>
using namespace std;
const int M = 1000000007;

int pal_length(const string& s_) {
    string s = "^" + s_;
    int n = s.length();
    vector<int> pl(n, M), gpl(n, M);
    pl[0] = 0;
    vector<tuple<int, int, int>> g;
    for (int j = 1; j < n; ++j) {
        vector<tuple<int, int, int>> g1, g2;
        for (auto [i, d, k] : g) {
            if (i > 0 && s[i - 1] == s[j]) {
                g1.emplace_back(i - 1, d, k);
            }
        }
        int r = -j;
        for (auto [i, d, k] : g1) {
            if (i - r != d) {
                g2.emplace_back(i, i - r, 1);
                if (k > 1) {
                    g2.emplace_back(i + d, d, k - 1);
                }
            }
            else {
                g2.emplace_back(i, d, k);
            }
            r = i + (k - 1) * d;
        }
        if (j > 1 && s[j - 1] == s[j]) {
            g2.emplace_back(j - 1, j - 1 - r, 1);
            r = j - 1;
        }
        g2.emplace_back(j, j - r, 1);
        g.clear();
        for (auto [i, d, k] : g2) {
            if (g.empty() || get<1>(g[(int)g.size() - 1]) != d) {
                g.emplace_back(i, d, k);
            }
            else {
                get<2>(g[(int)g.size() - 1]) += k;
            }
        }
        pl[j] = j;
        for (auto [i, d, k] : g) {
            r = i + (k - 1) * d;
            int m = pl[r - 1] + 1;
            if (k > 1) {
                m = min(m, gpl[i - d]);
            }
            if (d <= i) {
                gpl[i - d] = m;
            }
            pl[j] = min(pl[j], m);
        }
    }
    return pl[n - 1];
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    string s;
    cin >> s;
    cout << pal_length(s) << '\n';
    return 0;
}

palindromic_length.py

def pal_length(s_):
    s = "^" + s_
    n = len(s)
    pl = [0 for _ in range(n)]
    gpl = [n for _ in range(n)]
    g = []
    for j in range(1, n):
        g1 = [(i - 1, d, k) for i, d, k in g if i > 0 and s[i - 1] == s[j]]
        g2 = []
        r = -j
        for i, d, k in g1:
            if i - r != d:
                g2.append((i, i - r, 1))
                if k > 1:
                    g2.append((i + d, d, k - 1))
            else:
                g2.append((i, d, k))
            r = i + (k - 1) * d
        if j > 1 and s[j - 1] == s[j]:
            g2.append((j - 1, j - 1 - r, 1))
            r = j - 1
        g2.append((j, j - r, 1))
        g = []
        for i, d, k in g2:
            if not g or g[-1][1] != d:
                g.append((i, d, k))
            else:
                g[-1] = (g[-1][0], g[-1][1], g[-1][2] + k)
        pl[j] = j
        for i, d, k in g:
            r = i + (k - 1) * d
            m = pl[r - 1] + 1
            if k > 1:
                m = min(m, gpl[i - d])
            if d <= i:
                gpl[i - d] = m
            pl[j] = min(pl[j], m)
    return pl[-1]


print(pal_length(input()))

https://yukicoder.me/submissions/583133
https://yukicoder.me/submissions/583124

https://codeforces.com/contest/906/submission/99282798