洛谷2375 [NOI2014]动物园

Luogu

BZOJ

分析

$\mathrm{KMP}$ 。

首先求出 $nxt$ ,然后考虑怎么求 $num$ 。

发现 $num$ 的不重叠的限制似乎不太好搞,于是考虑先求出一个没有这个限制的数组 $tmp$ 。

发现对于一个前缀 $i$ ,满足既是它的前缀又是它的后缀的串是 $nxt[i]$ 、 $nxt[nxt[i]]$ 、...

那么在求 $nxt$ 的时候顺便把 $tmp$ 求出来就行了。具体的就是 $tmp[i]=tmp[nxt[i]]+1$ 。


现在有了 $tmp$ 就可以考虑求出 $num$ 了。

对于一个前缀 $i$ ,暴跳 $nxt$ 直到 $\text{当前的}nxt\text{值}*2\leq i$ 。

假设这个 $nxt$ 值为 $j$ ,那么 $num[i]=tmp[j]$ 。

但是如果每次暴跳的话,可能会被卡成 $o(n^2)$ 。于是仿照 $\mathrm{KMP}$ 的过程,保留上次的 $j$ 就行了。


具体实现和细节见代码。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
typedef long long ll;
using namespace std;

const int N=1000000+10;
const int mod=1e9+7;

char s[N];
int nxt[N],tmp[N],num[N];

int main() {
    int T; scanf("%d",&T);
    while (T--) {
        scanf("%s",s+1); int n=strlen(s+1);
        nxt[0]=-1,tmp[0]=0,tmp[1]=1;
        for (re int i=2,j=0;i<=n;++i) {
            while (j!=-1&&s[j+1]!=s[i]) j=nxt[j];
            nxt[i]=++j,tmp[i]=tmp[j]+1;
        }
        num[1]=0;
        for (re int i=2,j=0;i<=n;++i) {
            while (j!=-1&&s[j+1]!=s[i]) j=nxt[j];
            ++j;
            while (j*2>i) j=nxt[j];
            num[i]=tmp[j];
        }
        int ans=1;
        for (re int i=1;i<=n;++i) ans=1ll*ans*(num[i]+1)%mod;
        printf("%d\n",ans);
    }
    return 0;
}
最后修改:2019 年 09 月 25 日 01 : 38 PM

发表评论