题解 P2375 【[NOI2014]动物园】

NekoPass · 2019-11-06 22:07:41 · 题解

本题的精髓在于熟练掌握kmp以及递归转递推的思想，通过递推，我们就可以让 O(n^2) 变成 O(n)。如果您还不会kmp，可以前往此处学习OvO。

思路

在做本题之前，我们先来想一道这样的问题：

一个字符串s，求出它的 log 数组一一对于字符串s的前i个字符构成的子串，既是它的后缀同时又是它的前缀的字符串的数量(并且该前缀不能是字符串本身)。

比如字符串 ababa 的 log数组就是:

s[1]=0 \ ,\ s[2] = \ 0,\ s[3] = \ 1,\ s[4] = \ 1,\ s[5] = \ 2

对于这个问题，我们可以思考一下它和kmp的next数组(失配指针)的关系。我们知道，nex t数组可以代表一个字符串的前缀子字符串的 最长的既是它的前缀又是它的后缀的字符串的长度

比如字符串ababa的 next数组就是

next[1]=0 \ ,\ next[2] = \ 0,\ next[3] = \ 1,\ next[4] = \ 2,\ next[5] = \ 3

这个东西有什么用呢？我也不知道喵！

让我们把字符串和他的next列出来看看:

在我们求"ababa"的log数组的时候，我们的思路则是这样的:

诶，这怎么和递归next数组的过程一样呢？让我们画图来了解一下。

已知一个字符串的最长相同前后缀就是它的next(图中的蓝色下划线)，接着我们想要知道它剩下的相同前后缀(图中红色箭头)有哪些。

因为next是这个字符串的最长相同前后缀，所以剩下的相同前后缀绝对不会比它要长(这就是为什么图中红色箭头比蓝色下划线要短的原因)。

所以我们把这个字符串的next拿出来列在一起看，我们发现，这个字符串的次长相同前后缀，就是next的最长相同前后缀,也就是next的next。

所以，求log的过程，就是递归一个字符串的next的过程，可是一次次递归实在太慢了，所以我们把它转化成递推，得到了log数组的递推式:

log[x]=log[next[x]] + 1

PS:当next为0时，log等于0。

让我们回到题目：

求出一个更强大的 num 数组 一一 对于字符串 S的前 i个字符构成的子串，既是它的后缀同时又是它的前缀，并且该后缀与该前缀不重叠的字符串的数量。

很简单，我们直接放弃log的递推求法，改成递归，然后统计没超过字符串长度的一半的情况。这样我们就能快乐的TLE掉4个点。

那我们应该怎么办呢？再次模拟一下ababababa的递归过程看看吧！

显然，如果我们知道一个字符串的最长 不重叠相同前后缀 (对于ababababaa就是aba) 是什么，把它记成EXnext，我们就可以得到num的递推公式：

num[x]=log[EXnext[x]] + 1

PS:当EXnext为0时，log等于0。

所以本题的关键在于如何求出EXnext

回忆kmp算法的求解next的过程，我们发现，当一个前缀字符子串的next超过它的一半时，一定会先出现这样的情况:

容易发现，从左往右扫，重叠的情况一开始一定有且只有一个字符是重叠的。当我们求解EXnext时，一旦出现这种情况，就直接让EXnext=next[EXnext],这样我们就避免了重叠而且得到了最长的不重叠相同前后缀。

最后上代码，很丑请见谅QAQ:

#include <cstdio>
#define ll long long
using namespace std;
const int N=1000500;
const ll mod=1000000007;
int next[N],EXnext[N],len;
ll log[N],num[N];
char s[N];
inline void getnext(){
    int p=0;next[1]=0;
    for(int i=2;s[i];++i){
        while(p&&s[i]!=s[p+1]) p=next[p];
        if(s[i]==s[p+1]) ++p;
        next[i]=p;
    }
}
inline void getnum(){
    ll Ans=1;
    ll p=0;EXnext[1]=0;
    for(int i=2;s[i];++i){
        while(p&&s[i]!=s[p+1]) p=EXnext[p];
        if(s[i]==s[p+1]) ++p;
        if(i%2&&(i+1)/2==p) p=next[p];
        EXnext[i]=p;
    }
    for(int i=1;s[i];++i){
        log[i]=log[next[i]];
        if(EXnext[i]) ++log[i];
    }
    for(int i=1;s[i];++i){
        num[i]=log[EXnext[i]];
        if(EXnext[i]) ++num[i];
        Ans=(Ans*(num[i]+1))%mod;
    }
    printf("%lld\n",Ans);
}
int main(){
    int n;
    scanf("%d",&n);
    while(n--){
        scanf("%s",s+1);
        getnext();
        getnum();
    }
    return 0;
}