【题解】NOI2014动物园

一直到写到这道题目才发现我一直都理解了假的KMP……fail数组：fail[i]为从1-i(包含i)在内的字符串，相同的最长前后缀长度。

那么我们可以先思考暴力：先求出所有的fail，再不断往上跳，那么跳到的节点中(fail<<1)<i的个数即为num值。但这样的复杂度太高了，所以我们要进一步优化。

可以发现每一个节点所指向的fail节点是唯一的，但一个点可能是多个节点的fail，这是一个树形的关系。且在这个树形关系上，越靠近根节点的fail值也就越小。所以我们逐层标记Num值，直到找到符合条件的节点，则这个节点所标记的值就是它&它上方所有节点的个数。（若该点满足条件，则在它之上的一定满足）。

#include <bits/stdc++.h>

using namespace std;

#define maxn 10000

#define ll long long

#define p 1000000007

int fail[maxn], num[maxn];

char s[maxn];

ll solve()

{

    ll ans = ;

    int len = strlen(s + );

    memset(fail, , sizeof(fail));

    memset(num, , sizeof(num));

    num[] = ;

    for(int i = , j = ; i <= len; i ++)

    {

        while(j && s[i] != s[j + ]) j = fail[j];

        if(s[i] == s[j + ]) j ++;

        fail[i] = j;

        num[i] = num[j] + ;

    }

    for(int i = , j = ; i <= len; i ++)

    {

        while(j && s[i] != s[j + ]) j = fail[j];

        if(s[i] == s[j + ]) j ++;

        while((j << ) > i) j = fail[j];

        ans = (num[j] + ) * ans;

        ans %= p;

    }

    return ans;

}

int main()

{

    int T;

    scanf("%d", &T);

    while(T --)

    {

        scanf("%s", s + );

        printf("%lld\n", solve());

    }

    return ;

}

巴特西

【题解】NOI2014动物园

最新文章

热门文章