P3426

发表于 分类于
[POI2005]SZA-Template

[POI2005]SZA-Template

我们定义 $f(i)$ 表示 $[1,i]$ 的覆盖需要的最短长度。显然 $i$ 是 $f(i)$ 的最大取值。

考虑 $f(i)$ 的取值，$f(1)=1$ 显然。对于其他 $f(i)$，如果说 $[1,j]$ 可以被长度为 $x$ 的印章覆盖，且长度为 $x$ 的印章能盖出一个 $[1,i]$ 的公共前缀后缀（设长度为 $l$），并且 $l+j\ge i$，很显然我们就能通过这个长度为 $x$ 的前缀印章得到整个 $[1,i]$。

从另一个角度考虑，如果我们 KMP 后得到了 $nxt(i)$ 数组，表示 $[1,i)$ 的最长公共前缀后缀的长度，那么很显然 $f(i)$ 不是 $i$ 就是 $f(nxt(i+1))$（能覆盖 $[1,i]$ 的长度非 $i$ 的印章必然可以覆盖 $[1,nxt(i+1)]$）。

那么现在我们的问题转化为什么时候 $f(i)$ 可取 $f(nxt(i+1))$，显然根据上面的论述，只有在存在 $f(j)=f(nxt(i+1))$ 且 $j+nxt(i+1)\ge i$ 的时候可取。

具体实现中，开一个桶存储每个 $f$ 的值所对应的编号最大的 $i$ 是谁，然后需要的时候查询就行了。

时间复杂度 $O(n)$。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include<iostream>
#include<cstdio>
#include<cstring>
#define ll long long
using namespace std;
namespace Ehnaev{
  inline void write(ll x) {
    static char buf[22];static ll len=-1;
    if(x>=0) {do{buf[++len]=x%10+48;x/=10;}while(x);}
    else {putchar(45);do{buf[++len]=-(x%10)+48;x/=10;}while(x);}
    while(len>=0) putchar(buf[len--]);
  }
}using Ehnaev::write;

const ll N=1e6;

ll n;
ll nxt[N+5],buc[N+5],f[N+5];
char s[N+5];

int main() {

  scanf("%s",s+1);n=strlen(s+1);

  for(ll i=2;i<=n;i++) {
    ll j=nxt[i];
    while(j&&s[j+1]!=s[i]) j=nxt[j+1];
    j+=(s[j+1]==s[i]);nxt[i+1]=j;
  }

  f[1]=1;
  for(ll i=1;i<=n;i++) {
    if(buc[f[nxt[i+1]]]+nxt[i+1]>=i) f[i]=f[nxt[i+1]];
    else f[i]=i;buc[f[i]]=i;
  }

  write(f[n]);

  return 0;
}