题解 | #回文最少分割#

回文自动机+性质优化 DP。

时间复杂度 级别。

思路详见：https://oi-wiki.org/string/pam/ 。

//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 5e5 + 10;
char s[kN];
int n, f[kN], g[kN];
//=============================================================
//=============================================================
inline int read() {
  int f = 1, w = 0; char ch = getchar();
  for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0'); 
  return f * w;
}
namespace PAM {
  const int kNode = kN << 1;
  int nown, nodenum, last, tr[kNode][26], len[kNode], fail[kNode];
  int d[kNode], anc[kNode];
  char t[kN];
  int Newnode(int len_) {
    ++ nodenum;
    memset(tr[nodenum], 0, sizeof (tr[nodenum]));
    len[nodenum] = len_;
    fail[nodenum] = 0;
    return nodenum;
  }
  void Init() {
    nodenum = -1;
    last = 0;
    t[nown = 0] = '$';
    Newnode(0), Newnode(-1);
    fail[0] = 1;
  }
  int getfail(int x_) {
    while (t[nown - len[x_] - 1] != t[nown]) x_ = fail[x_];
    return x_;
  }
  void Insert(char ch_) {
    t[++ nown] = ch_;
    int now = getfail(last);
    if (!tr[now][ch_ - 'A']) {
      int x = Newnode(len[now] + 2);
      fail[x] = tr[getfail(fail[now])][ch_ - 'A'];
      tr[now][ch_ - 'A'] = x;
      d[x] = len[x] - len[fail[x]];
      anc[x] = (d[x] == d[fail[x]] ? anc[fail[x]] : fail[x]);
    }
    last = tr[now][ch_ - 'A'];
  }
  void DP(int i) {
    for (int j = last; j; j = anc[j]) {
      g[j] = i - len[anc[j]] - d[j];
      if (anc[j] != fail[j] && f[g[fail[j]]] < f[g[j]]) g[j] = g[fail[j]];
      if (f[g[j]] + 1 < f[i]) f[i] = f[g[j]] + 1;
    }
  }
}
//=============================================================
int main() {
  // freopen("1.txt", "r", stdin);
  scanf("%s", s + 1); n = strlen(s + 1);
  for (int i = 1; i <= n; ++ i) f[i] = kN;

  PAM::Init();
  for (int i = 1; i <= n; ++ i) {
    PAM::Insert(s[i]);
    PAM::DP(i);
  }
  printf("%d\n", f[n] - 1);
  return 0;
}