【题解】LOJ 2246 「NOI2014」动物园

Problem

给定一个字符串 $S$ ,求对于其任意一个前缀串,既是它前缀又是它后缀的且不相交的串有多少个

Thought

一般来说这样的题目我们会尝试使用 $KMP$ 来解决

我们需要求的应该就是对于任意前缀串前缀串 $s$ 有多少个长度 $\leq \frac{|s|}{2}$ 的前缀串是其后缀
利用 $KMP$ 建出的 $fail$ 树不难发现答案就是该节点的父亲中第一个长度 $\leq \frac{|s|}{2}$ 的串的深度

然后就按照建立 $fail$ 树的方式重新跑一边即可求出答案

P.S. 好像有可以一遍搞定的方法但是我实在懒得想了

Code

#include <bits/stdc++.h>
using namespace std;
int read() {
    int ans = 0, flag = 1;
    char ch = getchar();
    while(ch > '9' || ch < '0') {if(ch == '-') flag = - flag; ch = getchar();}
    while(ch >= '0' && ch <= '9') {ans = ans * 10 + ch - '0'; ch = getchar();}
    return ans * flag;
}

const int N = 1000010;
const int MOD = 1000000007;

char str[N];

int nxt[N];
int dep[N];
int ans[N];

void work() {
    scanf("%s", str);
    int len = strlen(str);
    int head = - 1, tail = 0;
    nxt[0] = - 1;
    dep[0] = 0;
    while(tail < len) {
        if(head == - 1 || str[head] == str[tail]) {
            nxt[++ tail] = ++ head;
            dep[tail] = dep[head] + 1;
        }
        else
            head = nxt[head];
    }
    head = - 1; tail = 0;
    long long ans = 1;
    while(tail < len) {
        if(head == - 1 || (str[head] == str[tail] && (head + 1) * 2 <= tail + 1)) {
            ++ tail;
            ans *= (dep[++ head] + 1);
            if(ans >= MOD) ans %= MOD;
        }
        else
            head = nxt[head];
    }
    printf("%lld\n", ans);
}

int main() {
    int T = read();
    while(T --) work();
    return 0;
}
Comments

添加新评论