题意
给定一个长度为 $n$ 的只包含小写字母的字符串 $S$。现在要在纸上印出字符串 $S$。
你可以刻一个印章，印章每使用一次，就会将印章上的所有字母印到纸上。同一个位置的相同字符可以印多次。但是，因为印上去的东西不能被抹掉，在同一位置上印不同字符是不允许的。求印章的最小长度。
例如：用 $\texttt{aba}$ 这个印章不可以印出 $\texttt{abcba}$。
$1 \leq n \leq 5 \times 10^5$
题解
考虑 DP。设 $f\left(i\right)$ 表示只取 $S$ 的前 $i$ 个字符的答案。
容易发现，$f\left(i\right)$ 的值，只有两种可能：$i$ 或 $f\left(next\left(i\right)\right)$。
其中的 $next\left(i\right)$ 表示 $S$ 中前 $i$ 个字符的公共前后缀数量（即 KMP 中的 $\texttt{next}$ 数组）。
原因是，要覆盖前 $i$ 个，起码覆盖前 $next\left(i\right)$ 个。
考虑 $f\left(i\right)$ 什么时候取 $f\left(next\left(i\right)\right)$：因为前缀 $i$ 的后缀为 $next\left(i\right)$，所以我们最多在后面接上 $next\left(i\right)$ 这么长的字符串，也就是如果存在一个 $j$，使得 $f\left(j\right) = f\left(next\left(i\right)\right)$ 且 $i - next\left(i\right) \leq j$，那么 $f\left(i\right)$ 就取 $f\left(next\left(i\right)\right)$。
代码
// By rbtree (https://rbtr.ee) :\
// Please submit with C++14!
#include <algorithm>
#include <array>
#include <cmath>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <tuple>
#include <unordered_map>
#include <utility>
#include <valarray>
#include <vector>
#define ra _Read_Int()
#define rc _Read_Char()
#define rs _Read_String()
#define rr _READ_RAW_::_Rd()
#define iotop _Get_IO_Top()
#ifdef ___RB_DEBUG___
#include "rb_debug.h"
#else
#define dbg(...)
#define dputs(...)
#endif
using tp = long long;
tp _Read_Int();
char _Read_Char();
bool _Get_IO_Top();
std::string _Read_String();
namespace _READ_RAW_ {
char _Rd();
} // namespace _READ_RAW_
using namespace std;
constexpr bool __MTCS__ = 0;
constexpr tp _BUF_SIZE_ = 2179217;
////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
namespace __SOL__ {
void main([[maybe_unused]] size_t __CASE__) { // :/
constexpr tp Hat_N = 5e5 + 3;
string s = ' ' + rs;
tp n = s.size() - 1;
array<tp, Hat_N> next, f, app;
next[0] = -1;
f[1] = 1;
app.fill(0);
app[1] = 1;
for (tp i = 2, j = 0; i <= n; next[i++] = ++j) {
for (; ~j && s[j + 1] != s[i]; j = next[j]) {
}
}
for (tp i = 2; i <= n; ++i) {
app[f[i] = app[f[next[i]]] >= i - next[i] ? f[next[i]] : i] = i;
}
printf("%lld\n", f[n]);
} // :)
} // namespace __SOL__
////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
signed main() {
tp __MTCS__ = ::__MTCS__ ? ra : 1;
for (tp __i = 1; __i <= __MTCS__; ++__i) {
__SOL__::main(__i);
}
return EXIT_SUCCESS;
}
namespace _READ_RAW_ {
std::array<char, _BUF_SIZE_> _BUF_;
std::array<char, _BUF_SIZE_>::iterator __Cur, __End = __Cur + 1;
char _Rd() {
if (++__Cur == __End) {
__Cur = _BUF_.begin();
__End = __Cur + fread(_BUF_.begin(), 1, _BUF_SIZE_, stdin);
}
return *__Cur;
}
} // namespace _READ_RAW_
bool _Get_IO_Top() {
if (_READ_RAW_::__Cur + 1 == _READ_RAW_::__End) {
_READ_RAW_::__Cur = _READ_RAW_::_BUF_.begin();
_READ_RAW_::__End = _READ_RAW_::__Cur +
fread(_READ_RAW_::_BUF_.begin(), 1, _BUF_SIZE_, stdin);
return _READ_RAW_::__Cur-- != _READ_RAW_::__End;
}
return 1;
}
tp _Read_Int() {
bool __neg(0);
char __c(_READ_RAW_::_Rd());
tp __val;
for (; __c < 48 || __c > 57; __c = _READ_RAW_::_Rd()) {
__neg = __c == 45;
}
__val = __c & 15;
for (__c = _READ_RAW_::_Rd(); __c > 47 && __c < 58; __c = _READ_RAW_::_Rd()) {
__val = __val * 10 + (__c & 15);
}
return __neg ? ~__val + 1 : __val;
}
char _Read_Char() {
char __c(_READ_RAW_::_Rd());
for (; __c == 32 || __c == 10 || __c == 13; __c = _READ_RAW_::_Rd()) {
}
return __c;
}
std::string _Read_String() {
char __c(_READ_RAW_::_Rd());
std::string __val;
for (; __c == 32 || __c == 10 || __c == 13; __c = _READ_RAW_::_Rd()) {
}
do {
__val.push_back(__c);
__c = _READ_RAW_::_Rd();
} while (__c != 32 && __c != 10 && __c != 13);
return __val;
}
/*#################################################################
#.................................................................#
#............................This.Code.Was.Created.By.RBTree......#
#.............#......#...............Limiting-Factor..............#
#............#.#....#.#.................Soul-Code.................#
#.............########............................................#
#............#........#..##############################...........#
#...........#..V....V......#..#........................#..#...#...#
#............#........#....#..........###..###..........#..#.#.#..#
#............#..X##X..#..#............#....#.#...........#..#...#.#
#...........#...N##N...#..#...........###..###..........#.........#
#.......MOE..#..@.....#....#.#.#.#...................#.#..........#
#.............########.....#.#.#.##############.#.#..#.#..........#
#..........................#.#.#.#.............#.#.#.#.#..........#
#......#########...........#.#.#.#.................#.#.#..........#
#.....#.........#..........#.#.#.#.................#.#.#..........#
#.#.#.#G#R#A#S#S#.#.#......#.#.#.#.................#.#.#..........#
#.###################......#.#.#.#.................#.#.#..........#
#...........................#.#.#...................#.#...........#
#.................................................................#
#################################################################*/