Menci

眉眼如初,岁月如故

在那无法确定的未来
只愿真心如现在一般清澈


「NOI2014」动物园 - KMP

对于字符串 S S 的前 i i 个字符构成的子串,既是它的后缀同时又是它的前缀,并且该后缀与该前缀不重叠,将这种字符串的数量记作 num(i) \mathrm {num}(i) ,求

链接

BZOJ 3670
UOJ #5

题解

考虑简化问题,去除「该后缀与该前缀不重叠」的限制后,问题变成了一个简单的 DP —— num(i)=num(next(i))+1 \mathrm{num}(i) = \mathrm{num}(\mathrm{next}(i)) + 1

考虑限制条件 —— 我们需要对 next \mathrm{next} 数组设置同样的限制条件,并设其为 next2 \mathrm{next2} 。然后对于带限制的 num \mathrm{num} (设为 num2 \mathrm{num2} ),发现 num2(i)=num2(next2(i))+1 \mathrm{num2}(i) = \mathrm{num2}(\mathrm{next2}(i)) + 1 并不成立,观察后可发现

num2(i)=num(next2(i))+1 \mathrm{num2}(i) = \mathrm{num}(\mathrm{next2}(i)) + 1

代码

#include <cstdio>
#include <cstring>

const int MAXT = 5;
const int MAXN = 1000000;
const unsigned long long MOD = 1000000007;

int n, next[MAXN + 1], next2[MAXN + 1], num[MAXN + 1], num2[MAXN + 1];
char s[MAXN + 1];

inline unsigned long long kmp() {
    next[0] = next[1] = num[0] = num[1] = 0;
    for (int i = 2, t = 0, k = 0; i <= n; i++) {
        while (t && s[t] != s[i - 1]) t = next[t];
        while ((k && s[k] != s[i - 1]) || k >= i / 2) k = next[k];

        if (s[k] == s[i - 1]) num2[i] = num[++k] + 1;
        else num2[i] = 0;

        if (s[t] == s[i - 1]) next[i] = ++t, num[i] = num[t] + 1;
        else next[i] = num[i] = 0;
    }

    // for (int i = 1; i <= n; i++) printf("%d%c", f[i], i == n ? '\n' : ' ');
    // for (int i = 1; i <= n; i++) printf("%d%c", num[i], i == n ? '\n' : ' ');
    // for (int i = 1; i <= n; i++) printf("%d%c", num2[i], i == n ? '\n' : ' ');

    unsigned long long ans = 1;
    for (int i = 1; i <= n; i++) (ans *= (num2[i] + 1)) %= MOD;
    return ans;
}

int main() {
    int t = 1;
    scanf("%d", &t);
    while (t--) {
        scanf("%s", s);
        n = strlen(s);

        printf("%llu\n", kmp());
    }

    return 0;
}