『KMP·Next树』[NOI2014]动物园

$\mathrm{P}\mathrm{r}\mathrm{o}\mathrm{b}\mathrm{l}\mathrm{e}\mathrm{m}$

$\mathrm{S}\mathrm{o}\mathrm{l}\mathrm{u}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}$

题目已经很明了了，可以知道这是一个KMP算法。在这里，我们引入next树的概念。

对于KMP中的某一个位置$i$，令$i$向$next[i]$连边，这样就形成了Next数。其中$0$号点表示空节点。

Next树有一下性质：

• 每一个节点的所有祖先（根节点除外）既是当前串的前缀也是当前串的后缀。
• 每一个节点的num数组即为祖先节点的数量。

显然，我们没有必要建出Next树，我们只需要令$num[i]=num[next[i]]+1$即可。

当然为了处理重复，当前节点的长度大于总串长度的一半就跳到父亲节点，知道小于等于一般为止。

代码如下：

#include <cstdio>
#include <string.h>
#include <iostream>using namespace std;
const int N = 2e6;
const int P = 1e9 + 7;int n;
char a[N];
int cnt[N], next[N];void work(void)
{
    int ans = 1;cin>>a+1;n = strlen(a+1);next[1] = (cnt[1] = 1) - 1;for (int i=2,j=0;i<=n;++i){
    while (j > 0 && a[i] != a[j+1]) j = next[j];if (a[i] == a[j+1]) j ++;next[i] = j, cnt[i] = cnt[j] + 1;}for (int i=2,j=0;i<=n;++i){
    while (j > 0 && a[i] != a[j+1]) j = next[j];if (a[i] == a[j+1]) j ++;while (j > i / 2) j = next[j];ans = 1LL * ans * (cnt[j]+1) % P;  }cout<<ans<<endl;return;
}int main(void)
{
    freopen("zoo.in","r",stdin);freopen("zoo.out","w",stdout);int T; cin>>T;while (T --) work();return 0;
}