这题的题解多为远古题解，故读起来多有误解与盲区，因此写了这篇题解。

题目简述

给定你要印刷的文本串 $S$。

你决定刻一个印章，印章每使用一次，就会将印章上的所有字母印到纸上。

同一个位置的相同字符可以印多次。例如：用 aba 这个印章可以完成印制 ababa 的工作（中间的 a 被印了两次）。但是，因为印上去的东西不能被抹掉，在同一位置上印不同字符是不允许的。例如：用 aba 这个印章不可以完成印制 abcba 的工作。

你希望印章的字符串长度尽可能小。

思路

以下是我们的约定 & 发现：

• $s$ 可以被 $t$ 印刷，当且仅当可以通过若干次印印章 $t$ 得到一字符串 $T$，使得 $s$ 是 $T$ 的子串。

• $s$ 正好被 $t$ 印刷，当且仅当可以通过若干次印印章 $t$ 得到一字符串 $T$，使得 $s = T$。

• $s[l,r]$ 表示 $s_{l}s_{l+1}\dots s_{r}$。

• $t$ 是 $s$ 的 $\text{Border}$ 当且仅当 $t$ 既是 $s$ 的前缀，也是 $s$ 的后缀，可以发现若 $s$ 正好被印刷必有印章 $t$ 是其的 $\text{Border}$。

• $t$ 是 $s$ 的真 $\text{Border}$ 当且仅当 $t$ 既是 $s$ 的前缀，也是 $s$ 的后缀，且 $s \ne t$，同时定义 $nxt_i$ 表示 $S[1,i]$ 的最长真 $\text{Border}$ 长度。

• 字符串 $s$ 的任意真 $\text{Border}$ 一定是 $s$ 最长真 $\text{Border}$ 的 $\text{Border}$。（有点绕，可以画下图，这里简单解释一下，其实就是 KMP 的一些思想）

• 由上一条可以推广到对于任意的印章 $t$，若 $t$ 是 $s$ 的真 $\text{Border}$，且正好印刷 $s$，则 $t$ 也可以正好印刷 $s$ 的最长真 $\text{Border}$。（解释）

考虑 DP，令 $dp_i$ 表示将 $S[1,i]$ 正好印刷所需的最小印章长度。

可以发现，$dp_i$ 只可能等于 $i$ 或 $dp_{nxt_i}$，$dp_i = i$ 很显然，直接令印章 $T = S[1,i]$ 即可，而 $dp_i=dp_{nxt_i}$ 可以用上述中的第 $7$ 条理解。

但不是何时都能等于 $dp_{nxt_i}$，又是那个例子，假设 $S[1,i]$ 长 $24$，形如这样：#######__________#######。

可以发现，中间有 $10$ 个其他字符，如果印章长度只有 $dp_{nxt_i}$ 可能印刷不到，那么何时才能取 $dp_{nxt_i}$ 呢？

而只要我们把中间一段覆盖到就可以取到 $dp_{nxt_i}$，就比如这样：

#######__________#######
                 #######
$$$$$$$$$$$$$$$$$ 第一种：正好与后面一段的 Border 衔接
$$$$$$$$$$$$$$$$$$$$ 第二种：与后面一段的 Border 有交集

即需存在 $j$，使得 $dp_j = dp_{nxt_i}$（显然 $S[1,j]$ 与 $S[1,nxt_i]$ 使用的印章要相同吧？） 且 $i - nxt_i \le j < i$，实现时开个桶就行。

这里略微解释下为什么 $dp_j = dp_{nxt_i}$ 则 $S[1,j]$ 与 $S[1,nxt_i]$ 使用的印章相同，因为“若 $s$ 正好被印刷必有印章 $t$ 是其的 $\text{Border}$” 由 $\text{Border}$ 的定义有 $t$ 是 $s$ 的前缀，所以 $S[1,nxt_i]$ 使用的印章为 $S[1,dp_{nxt_i}]$，$S[1,j]$ 使用的印章为 $S[1,dp_j]$，又因为 $dp_j = dp_{nxt_{i}}$，所以它俩用的印章相同。

具体实现见代码。

复杂度分析

• 时间复杂度：KMP 求 $nxt$ 数组 $O(n)$，DP 也是 $O(n)$，总共 $O(n)$。

• 空间复杂度：$O(n)$。

#include<bits/stdc++.h>

using namespace std;
using ll = long long;

const int MAXN = 5e5 + 5;

string s;
int n, nxt[MAXN], dp[MAXN], t[MAXN];

int main(){
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> s;
  n = s.size(), s = "#" + s;
  for(int i = 2; i <= n; i++){
    int pos = nxt[i - 1];
    for(; pos && s[i] != s[pos + 1]; pos = nxt[pos]);
    nxt[i] = s[i] == s[pos + 1] ? pos + 1 : 0;
  }//KMP 求 nxt 数组
  dp[1] = 1, t[dp[1]] = 1;//注意初始化问题
  for(int i = 2; i <= n; i++){
    if(t[dp[nxt[i]]] >= i - nxt[i]){//存在符合要求的 j
      dp[i] = dp[nxt[i]];
    }else{
      dp[i] = i;//否则只能为 i
    }
    t[dp[i]] = i;//只取 dp[i] 相同的 i 的最大值
  }
  cout << dp[n];
  return 0;
}