[KMP-fail树]BZOJ3670(Noi2014)【动物园】题解

Author Avatar
ZigZagK 2018年9月9日 16:28
remove_red_eye 14

题目概述

一个字符串,令 $num_{i}$ 表示前缀 $i$ 的长度 $\le{i\over 2}$ 的 $border$ 数量,求 $\prod_{i=1}^{n}num_i+1$ 。

解题报告

$border$ 数量就是 $fail$ 树上的深度,由于长度不能超过 ${i\over 2}$ 所以只需要沿 $fail$ 树跳找到 $dep_x\le {i\over 2}$ 的 $dep_x$ 。

复杂度的话应该是 $O(n)$ 吧?感觉后面的复杂度比前面小……

示例程序

#include<cstdio>
#include<cstring>
using namespace std;
typedef long long LL;
const int maxn=1000000,MOD=1e9+7;

int te,n,fai[maxn+5],num[maxn+5],ans;char s[maxn+5];

inline void getnum(){
    for (int i=2,j=(num[1]=1,0);i<=n;i++){
        while (j&&s[j+1]!=s[i]) j=fai[j];
        j+=s[j+1]==s[i];num[i]=num[j]+1;fai[i]=j;
    }
    for (int i=2,j=0;i<=n;i++){
        while (j&&s[j+1]!=s[i]) j=fai[j];
        j+=s[j+1]==s[i];while (j>(i>>1)) j=fai[j];ans=(LL)ans*(num[j]+1)%MOD;
    }
}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    for (scanf("%d",&te);te;te--) scanf("%s",s+1),n=strlen(s+1),ans=1,getnum(),printf("%d\n",ans);return 0;
}

本文链接:https://zigzagk.top/2018/09/09/BZOJ3670
本博客所有文章除特别声明外,均采用CC BY-NC-SA 4.0 CN 许可协议。转载请注明作者和出处QwQ。