首页 > 代码库 > BZOJ 3620: 似乎在梦中见过的样子 [KMP 暴力]
BZOJ 3620: 似乎在梦中见过的样子 [KMP 暴力]
和我签订契约，成为魔法少女吧
题意：求所有形似于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=15005,MOD=1e9+7;int n,k,ans;char s[N];int fail[N],sum[N];void KMP(char s[],int n){ fail[1]=0; for(int i=2;i<=n;i++){ int j=fail[i-1]; while(j&&s[i]!=s[j+1]) j=fail[j]; fail[i]=s[i]==s[j+1]?j+1:0; } int j=0; for(int i=2;i<=n;i++){ while(j&&s[i]!=s[j+1]) j=fail[j]; if(s[i]==s[j+1]) j++; while((j<<1)>i-1) j=fail[j]; ans+=j>=k; }}int main(){ freopen("in","r",stdin); scanf("%s%d",s+1,&k); n=strlen(s+1); int _=n-(k<<1); for(int i=0;i<_;i++) KMP(s+i,n-i); printf("%d",ans);}
BZOJ 3620: 似乎在梦中见过的样子 [KMP 暴力]
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。