[BZOJ3670][Noi2014]动物园（KMP）_bzoj3670动物园-CSDN博客

本文链接：https://blog.csdn.net/FromATP/article/details/53143464

=== ===

题解

写这题的时候我还不会在本机开栈，为了写对拍硬生生把dfs改成了非递归。。。然后这代码就看起来超长。。。。

这道题的意思是对于一个字符串定义一个num[i]为前缀p[1..i-1]中满足“既是前缀p[i]的前缀（啊废话那肯定是它的前缀）又是它的后缀并且前缀和后缀不重叠”的数目，然后要对整个串求一个 $\sum \limits_{i=1}^n num[i]$ 。显然这玩意儿跟KMP里面的失配函数有很大关系。。并且很容易想到一种暴力求num数组的做法就是对于每个位置顺着失配函数next一路追溯到0，统计next值小于等于i/2的就可以了。目测随机数据这种做法差不多能过，但是如果像是整个串都是同一种字符的那种的话它就稳稳 $n^2$ 了。。。

观察这个暴力，它很暴力的原因就是每次向前蹦的时候很多位置被重复跳了很多次，并且一旦跳到了以前跳过的位置，接下来跳的情况就跟以前相同了。所以如果能对每个走过的节点维护信息，然后保证每个点只经过一遍，就能把这个时间复杂度压到科学的 $O(n)$ 。

观察失配函数的建立过程，我们可以发现一个点只会连到唯一的一个点，但是可能被很多点连到。这是一个标准的树结构，那么如果把树上每个点的权值赋值为它的next值，我们要求的就是对每个点它到树根的路径上有多少个点的权值大于i/2。那么我们可以发现一条链上的点好像是可以一块求的。如果维护一个指针指向对于当前点i，满足条件的最靠下的一个祖先，那显然上面的所有点都满足条件，那么答案就是deep值；并且随着i的下移，这个指针的位置是单调不上升的。于是在dfs中维护这个指针，每次让它尽量下移，然后统计deep。记录一下这条路径从哪条边走过来便于指针下放。注意指针不能移动到当前节点的下面否则就不是它的祖先了。所以要加一条特判，好像在失配函数有连续一大段为0的时候会起作用。

代码

#include<cstdio>
#include<cstring>
#include<algorithm>
#define Mod 1000000007
using namespace std;
int n,len,tot,p[1000010],a[2000010],next[2000010],T[1000010],cur[1000010],fa[1000010],e[1000010],flast[1000010],fdep[1000010];
char S[1000010];
bool vis[1000010];
void add(int x,int y){tot++;a[tot]=y;next[tot]=p[x];p[x]=tot;}
long long ans;
/*void dfs(int u,int last,int deep){
    int x=a[cur[last]],nowdep=deep;
    while (T[x]<=u/2&&u!=0){
        last=x;nowdep+=1;
        if (x==u) break;
        x=a[cur[last]];
    }
    if (u!=0) ans=ans*(nowdep+1)%Mod;
    for (int i=p[u];i!=0;i=next[i]){
        cur[u]=i;dfs(a[i],last,nowdep);
    }
}*/
void dfs(){
    int u=0,last=0,deep=-1;
    bool flag;
    while (true){
        if (vis[u]==false){
            int x=a[cur[last]];
            vis[u]=true;
            while (T[x]<=u/2&&u!=0){//如果这个祖先不符合要求并且还可以再下移
                last=x;deep+=1;//deep维护当前祖先的深度
                if (x==u) break;
                x=a[cur[last]];//顺着当前路径下移
            }
            if (u!=0) ans=ans*(deep+1)%Mod;
        }
        flag=false;
        for (int i=e[u];i!=0;i=next[i]){
            cur[u]=i;e[u]=next[i];
            fa[a[i]]=u;flast[a[i]]=last;
            fdep[a[i]]=deep;u=a[i];
            flag=true;break;
        }
        if (flag==false){
            if (u==0) break;
            last=flast[u];deep=fdep[u];
            u=fa[u];//得到上一层的信息并回溯
        }
    }
}
int main()
{
    scanf("%d",&n);
    for (int wer=1;wer<=n;wer++){
        memset(p,0,sizeof(p));
        T[0]=-1;tot=0;
        scanf("%s",S);
        len=strlen(S);
        for (int i=0;i<len;i++){
            int j=T[i],pos=i;
            while (j!=-1&&S[j]!=S[i])
            {pos=j;j=T[j];}
            T[i+1]=j+1;
            add(j+1,i+1);//建立KMP树
        }
        for (int i=0;i<=len;i++){
            cur[i]=p[i];e[i]=p[i];vis[i]=false;
        }
        ans=1;dfs();
        printf("%I64d\n",ans%Mod);
    }
    return 0;
}