Description

Luogu2375

Solution

KMP神题。
首先注意到这个题一定要考KMP，所以先做一遍KMP再说。然后仔细观察就可以发现，在不管前后缀是否相交的情况下，\(ans[i] = ans[next[i]] + 1\)，这里加上的那个\(1\)是前后缀都是原串的情况。然后怎么处理前后缀不相交呢，一个简单的思路就是让\(next[i] < i / 2\)就好了。但是如果在做KMP的时候判掉这个会导致之后的转移不对，在KMP之后暴力的跳也会导致TLE。于是我们观察发现：如果\(next[i] > i / 2\)的话，那么\(next[i] + 1 > (i+1) / 2\)显然成立。所以在跳第一下的时候是可以跳到满足\(next[i-1] < (i-1) / 2\)的\(next[i-1]\)的。（这里还是看代码吧，不大好用文字描述）。然后就可以做两边KMP，第一遍是正常的KMP，第二遍要求\(Next[i] < i / 2\)，这样的话，\(num[i] = ans[Next[i]]\)。

Code

#include <cstdio>
#include <cstring>

const int N = 1e6 + 10;
typedef long long LL;
const LL MOD = 1e9 + 7;

char s[N];
int nxt[N], cnt[N], Nxt[N];
/*nxt是正常的next数组，Nxt是要求Nxt[i] < i / 2的next数组*/
LL ans, len;

void work1() {
    for (int i = 1; i <= len; ++i) {
        int t = nxt[i - 1];
        while (t != -1 && s[t+1] != s[i]) t = nxt[t];
        nxt[i] = t+1; 
        cnt[i] = cnt[t+1] + 1;
    }
}

void work2() {
    for (int i = 1; i <= len; ++i) {
        int t = Nxt[i-1];
        if (t + 1 > i / 2) t = nxt[t];
        while (t != -1 && s[t+1] != s[i]) t = nxt[t];
        Nxt[i] = t+1;
    }
}

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        scanf("%s", s+1);
        len = strlen(s+1);
        Nxt[0] = nxt[0] = -1;
        work1();
        work2();
        ans = 1;
        for (int i = 1; i <= len; ++i) ans = ans * (cnt[Nxt[i]] + 1) % MOD;
        printf("%lld\n", ans);
    }
    return 0;
}

Note

做了这个题我忽然发现我的KMP还没有后缀数组掌握的好，真不知道我一直在学啥。

[NOI2014]动物园

原文：https://www.cnblogs.com/wyxwyx/p/noi2014zoo.html