Description

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 
    
     #include 
     
      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还没有后缀数组掌握的好，真不知道我一直在学啥。