「NOI2014」动物园

#include <bits/stdc++.h>
using namespace std;
#define next next233

const int MAXN = 1e6 + 5;
const int MOD = 1e9 + 7;

int next[MAXN], num[MAXN];

void exKMP_pre(char *T) {
    int n = strlen(T);
    next[0] = n;
    int p = 0;
    while (p + 1 < n && T[p] == T[p + 1]) p++;
    next[1] = p;
    int k = 1;
    for (int x = 2; x < n; ++x) {
        p = k + next[k] - 1;
        int l = next[x - k];
        if (x + l <= p) next[x] = l;
        else {
            int j = p - x + 1;
            if (j < 0) j = 0;
            while (x + j < n && T[x + j] == T[j]) j++;
            next[x] = j;
            k = x;
        }
    }
}

int T, ans;
char a[MAXN];

int main() {
    scanf("%d", &T);
    while (T--) {
        memset(next, 0, sizeof(next));
        memset(num, 0, sizeof(num));
        cin >> a;
        exKMP_pre(a);
        int n = strlen(a);
        for (int i = 1; i < n; ++i) {
            if (next[i]) {
                num[i] ++;
                num[min(i + next[i], i << 1)]--;
            }
        }
        ans = 1;
        for (int i = 1; i < n; ++i) {
            num[i] += num[i - 1];
            ans = 1ll * ans * (num[i] + 1) % MOD;
        }
        printf("%d\n", ans);
    }
    return 0;
}