动物园 TJ

· · 题解

动物园 TJ

题目链接

题目大意

意思简介明了，即求一个类似于KMP中next数组的数组num，但要求该最长公共前后缀不重合

前置芝士：KMP模式匹配算法

思路

当我们求出next数组时，我们就可以顺便求出num数组的一个变体：公共前后缀有重合的情况下的数量。记为cnt数组

此基础下，我们可以通过next往前查询，因为next[i]与i之间一定是满足next[i]<i的，因此我们通过这样的跳跃，就能找到最后一个公共前后缀不重合的情况

这个过程类似于next的求解，因此正确性很好证明

于是就有了此部分核心代码：

nex[0]=-1,nex[1]=0,cnt[0]=0,cnt[1]=1;
for(int j=0,k=-1;j<t.length();){//求解next数组
    if(k==-1||t[j]==t[k]) nex[++j]=++k,cnt[j]=cnt[k]+1;//更新cnt数组（方法类似与next，不过统计的是数量）
    else k=nex[k];//跳转，继续求解
}
unsigned long long ans=1;//最后答案
for(int j=0,k=-1;j<t.length();){
    if(k!=-1&&t[j]!=t[k]) k=nex[k];//等同与next数组求解时的跳转
    else{
        k++,j++;//更新长度
        while((k<<1)>j) k=nex[k];//疯狂跳转，当长度不大于子串长度一半时即可停止（此时已没有重合）
        ans=(ans*(cnt[k]+1))%1000000007;//num数组就不存了，直接进行计算
    }
}

最后得到的ans即为答案