BZOJ 3620: 似乎在梦中见过的样子 [KMP 暴力]

时间：2023-03-08 17:29:27

和我签订契约，成为魔法少女吧

题意：求所有形似于A+B+A 的子串的数量 , 且len(A)>=k,len(B)>=1

位置不同其他性质相同的子串算不同子串,位置相同但拆分不同的子串算同一子串

竟然是暴力........

枚举从哪里开始，和上题一样了

只不过本题$l$确定后一个$r$只能贡献一次，所以向前找第一个$2*j \le i-1$的位置判断$j \ge k$就行了

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

using namespace std;

typedef long long ll;

const int N=,MOD=1e9+;

int n,k,ans;

char s[N];

int fail[N],sum[N];

void KMP(char s[],int n){

    fail[]=;

    for(int i=;i<=n;i++){

        int j=fail[i-];

        while(j&&s[i]!=s[j+]) j=fail[j];

        fail[i]=s[i]==s[j+]?j+:;

    }

    int j=;

    for(int i=;i<=n;i++){

        while(j&&s[i]!=s[j+]) j=fail[j];

        if(s[i]==s[j+]) j++;

        while((j<<)>i-) j=fail[j];

        ans+=j>=k;

    }

}

int main(){

    freopen("in","r",stdin);

    scanf("%s%d",s+,&k);

    n=strlen(s+);

    int _=n-(k<<);

    for(int i=;i<_;i++) KMP(s+i,n-i);

    printf("%d",ans);

}

相关文章