BZOJ 3670 - [Noi2014]动物园

#kmp
Published on 2016-05-16

题目地址

描述

UOJ 传送门：【NOI2014】动物园

分析

分析后就能发现，num(i)\mathrm{num}(i) 的值并不是 min{12i,next(i)}\min\{\frac 1 2 i, \mathrm{next}(i)\}，因为每次在缩的过程中，缩的分别是第一个和最后一个字符，剩余部分不一定相等。（如果你没有陷入这样的问题或者没看懂我在说什么，那么可忽略）。

那 num(i)\mathrm{num}(i) 等于什么呢？如果没有限制的话，设 cnt(i)\mathrm{cnt}(i) 为经过几次 i=f(i)i = f(i) 的变换之后得到 0，则 num(i)=cnt(next(i))+1\mathrm{num}(i) = \mathrm{cnt}(\mathrm{next}(i)) + 1。
可题目是有限制的，如果我们能求出 g(i)g(i) 表示最长的不超过 12i\frac 1 2 i 的值，则所求的 num(i)=cnt(g(i))+1\mathrm{num}(i) = \mathrm{cnt}(g(i)) + 1。我们可以通过再做一次 KMP，每次保证 gg 的值总是小于 12i\frac 1 2 i 且最大，不断的递推下去，就能得到正确的答案。

难道我们我们只从 g(i)g(i) 推到 g(i+1)g(i + 1) 的话，不会导致不够优吗？不会，因为根据题目不超过 12i\frac 1 2 i 的限制，有g(i+1)≤g(i)+1g(i + 1) \le g(i) + 1，而我们每次转移最多可以 +1，所以肯定是正确的。

代码

//  Created by Sengxian on 5/16/16.
//  Copyright (c) 2016年 Sengxian. All rights reserved.
//  BZOJ 3669 NOI 2014 D2T1 带限制 KMP
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
inline int ReadInt() {
    static int n, ch;
    n = 0, ch = getchar();
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) n = (n << 3) + (n << 1) + ch - '0', ch = getchar();
    return n;
}

const int maxn = 1000000 + 3, modu = 1000000007;
char str[maxn];
int f[maxn], g[maxn], cnt[maxn];

int main() {
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
#endif
    int caseNum = ReadInt();
    f[0] = 0, f[1] = 0, g[0] = 0, g[1] = 0, cnt[0] = 0, cnt[1] = 1;
    while (caseNum--) {
        scanf("%s", str);
        int n = strlen(str);

        for (int i = 1; i < n; ++i) {
            int j = f[i];
            while (j && str[i] != str[j]) j = f[j];
            f[i + 1] = str[i] == str[j] ? j + 1 : 0;
            cnt[i + 1] = cnt[f[i + 1]] + 1;
        }

        for (int i = 2; i <= n; ++i) {
            int j = g[i - 1]; //直接使用前一个，并不会丢失最优解
            while (j && str[i - 1] != str[j]) j = f[j];
            g[i] = str[i - 1] == str[j] ? j + 1 : 0;
            if (g[i] > i / 2) g[i] = f[g[i]]; //如果超出范围，则退回
        }

        ll ans = 1;
        for (int i = 1; i <= n; ++i) (ans *= cnt[g[i]] + 1) %= modu;
        printf("%lld\n", ans);
    }
    return 0;
}
BZOJ 3243 - [Noi2013]向量内积