首页 > 代码库 > BZOJ 3942 Censoring
BZOJ 3942 Censoring
KMP。
怎么描述做法呢。。。“持久化”一下?
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define maxn 1000050 using namespace std; char s[maxn],t[maxn]; int l1,l2,nxt[maxn],pre[maxn],aft[maxn],ts[maxn]; bool flag[maxn]; void get_nxt() { int cnt=0; for (int i=2;i<=l1;i++) { while (cnt && s[cnt]!=s[i-1]) cnt=nxt[cnt]; if (s[cnt]==s[i-1]) cnt++; nxt[i]=cnt; } for (int i=0;i<=l2;i++) pre[i]=i-1,aft[i]=i+1; aft[l2-1]=-1; } void kmp() { int cnt=0; for (int i=0;i<l2;i++) { while (cnt && s[cnt]!=t[i]) cnt=nxt[cnt]; if (s[cnt]==t[i]) cnt++; ts[i]=cnt; if (cnt==l1) { int now=i; for (int j=1;j<=l1;j++) { flag[now]=true; now=pre[now]; } cnt=ts[now];pre[i+1]=now; } } } int main() { scanf("%s",t);l2=strlen(t); scanf("%s",s);l1=strlen(s); get_nxt(); kmp(); for (int i=0;i<l2;i++) if (!flag[i]) printf("%c",t[i]); printf("\n"); return 0; }
BZOJ 3942 Censoring
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。