题解P3426 [POI2005]SZA-Template

· · 题解

蒟蒻的博客链接：本题题解

KMP学习笔记链接：KMP

题目链接：传送门

Byteasar想在墙上涂一段很长的字符,他为了做这件事从字符的前面一段中截取了一段作为模版. 然后将模版重复喷涂到相应的位置后就得到了他想要的字符序列.一个字符可以被覆盖很多次,但是一个位置不能填不同的字符.做一个模版很费工夫,所以他想要模版的长度尽量小,求最小长度是多少。

大体思路：

先用kmp求出字符串的next数组，然后dp。（以下next记为nxt）

让f[i]表示前缀为i的模板长度的最小值。

先证明几个引理。

注明： 用来覆盖一个序列的模版一定是字符串的前缀，但在下文中有些地方称为“长度为XXX的串”，意思是"长度为XXX的前缀"。

引理一、f[i]的取值只能为i或者f[nxt[i]]

引理1.1 f[i]<=i

这个很显然。。因为用这个字符串本身一定能覆盖前i个字符qwq

引理1.2 f[i]>=f[nxt[i]]

如果f[i]<f[nxt[i]]，那么就无法用f[i]的长度来填充前nxt[i]个字符（否则f[nxt[i]]会更小，就矛盾了）

引理1.3 若f[i]<i，则f[i]<=nxt[i]

证明：如果f[i]>nxt[i]，则长度为f[i]时，能使此字符串的前后缀相同（如图所示，两段红色的区域是相同的）。

因为必须有一个长度f[i]的串在最前面，有一个长度f[i]的串在最后面，否则前面或后面会覆盖不到qwq。

这与nxt[i]是最大的使前后缀相同的长度矛盾，所以f[i]<=nxt[i]。

引理1.4 若f[i]<nxt[i]，那么f[i]=f[nxt[i]]

证明：当f[nxt[i]]<f[i]<nxt[i]时，覆盖情况如图所示。

由f[i]的定义，能用长度为f[i]的串来覆盖完前i个字符，且能用长度f[nxt[i]]的串覆盖前nxt[i]个字符。

所以珂以用前f[nxt[i]]的串来覆盖长度为f[i]的串（因为f[i]<nxt[i]），这与f[i]是最小的能覆盖前i个字符的长度矛盾。

因此f[nxt[i]]<f[i]<nxt[i]不成立。

由引理1.2，f[i]>=f[nxt[i]]。由已知，f[i]<nxt[i]。 所以f[i]=f[nxt[i]]。

引理1.5 若f[i]=nxt[i]，则f[nxt[i]]=nxt[i]，即f[i]=f[nxt[i]]。

图与引理1.4类似，就不画了qwq。

因为f[i]=nxt[i]，所以珂以用长度nxt[i]的串来覆盖前i个字符，且不能用长度比nxt[i]小的串来覆盖前i个。

因此前nxt[i]个字符和后nxt[i]个字符之间的部分（注意这部分可能为空，即前后nxt[i]个可能重叠）也可以用长度为nxt[i]的前缀来覆盖。

若f[nxt[i]] \not=nxt[i]，由引理1.1，只可能是f[nxt[i]]<nxt[i]的情况。

因为可以用长度为f[nxt[i]]的串来覆盖前nxt[i]个。

因此珂以把覆盖前i个字符的长度为nxt[i]的串都换成长度为f[nxt[i]]的串。

此时f[i]应为f[nxt[i]]，而f[nxt[i]]<f[i]，矛盾。

因此f[i]=f[nxt[i]]=nxt[i]。

综上，

由引理1.1和引理1.2，有f[nxt[i]]<=f[i]<=i。

由引理1.3，有f[nxt[i]]<=f[i]<=nxt[i]或f[i]=i。

由引理1.4和引理1.5，当f[i]<=nxt[i]时，f[i]=f[nxt[i]]。

因此f[i]=f[nxt[i]]或f[i]=i。

引理二、f[i]=f[nxt[i]]的充要条件是存在j \in [i-nxt[i],i)，f[j]=f[nxt[i]]

引理2.1 引理二的充分性证明，即f[i]=f[nxt[i]] => ∃j\in[i-nxt[i],i],f[j]=f[nxt[i]]

在[i-nxt[i],i]之间任意一处取一个j，发现[1,j]之间一定能被红色线段覆盖。

因此可以证明引理二的充分性。

引理2.2 引理二的必要性证明，即∃j\in[i-nxt[i],i],f[j]=f[nxt[i]]=>f[i]=f[nxt[i]]。

图与引理2.1的证明类似，就不画了qwq。

因为∃j\in[i-nxt[i],i],f[j]=f[nxt[i]]，且由f[nxt[i]]的定义，长度为f[nxt[i]]的串能覆盖前nxt[i]个字符，

所以(i-nxt[i],i]之间的字符也可以用f[nxt[i]]的长度的串覆盖。

又因为[1,j]的字符可以用f[nxt[i]]的长度的串覆盖，且j>=i-nxt[i]，

所以[1,i]的字符可以用f[nxt[i]]的长度的串覆盖。

由引理一，f[i]=f[nxt[i]]或i。

由引理1.1，f[nxt[i]]<=nxt[i]<i，即f[nxt[i]]<i，

所以f[i]=f[nxt[i]]。

综上，

由引理2.1和引理2.2，引理二得证。

重复一次引理：

引理一、f[i]=f[nxt[i]]或i（f[nxt[i]]<i）

引理二、f[i]=f[nxt[i]]<=>存在j\in[i-nxt[i],i]，f[j]=f[nxt[i]]

然后看这道题：

先kmp跑出nxt数组，然后用一个数组记录每个f值出现的最新位置。

遍历1~n，若f[nxt[i]]出现的最新位置>=i-nxt[i]，则f[i]=f[nxt[i]]，否则为i。

毒瘤代码

#include<stdio.h>
#include<cstring>
#include<algorithm>
#include<math.h>
#define re register int
using namespace std;
typedef long long ll;
int read() {
    re x=0,f=1;
    char ch=getchar();
    while(ch<'0' || ch>'9') {
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9') {
        x=10*x+ch-'0';
        ch=getchar();
    }
    return x*f;
}
const int Size=500005;
int n,b[Size],f[Size],nxt[Size];
char str[Size];
int main() {
//  n=read();
    scanf("%s",str+1);
    n=strlen(str+1);
    int j=0;
    for(re i=2; i<=n; i++) {
        while(j>0 && str[j+1]!=str[i])  j=nxt[j];
        if(str[j+1]==str[i])    j++;
        nxt[i]=j;
    }
    for(re i=2; i<=n; i++) {
        f[i]=i;
        if(b[f[nxt[i]]]>=i-nxt[i]) {
            f[i]=f[nxt[i]];
        }
        b[f[i]]=i;
    }
    printf("%d",f[n]);
    return 0;
}