P4824 [USACO15FEB]Censoring S 题解

题面

本来就是个裸的KMP，但是这个题是有删除的，所以可以维护一个栈，每次的 \(j\) 都继承栈顶元素的 \(j\)，然后如果找到了一个匹配，就直接弹栈即可。因为只会进栈 \(O(n)\) 次，所以总复杂度也是 \(O(n)\) 的。这个题算是栈的妙用了。

点击查看代码

#include<iostream>#include<cstdio>#include<cstring>#include<stack>using namespace std;const int N=1e6+13;char s[N],t[N];bool vis[N];int n,m,nxt[N],pos[N];inline void init(){nxt[1]=0;for(int i=2,j=0;i<=m;++i){while(j&&t[j+1]!=t[i]) j=nxt[j];if(t[j+1]==t[i]) ++j;nxt[i]=j;}}inline void KMP(){stack<int> st;st.push(0);for(int i=1;i<=n;++i){int j=pos[st.top()];while(j&&t[j+1]!=s[i]) j=nxt[j];if(t[j+1]==s[i]) ++j;if(j==m){vis[i]=1,--j;while(j--) vis[st.top()]=1,st.pop();}else st.push(i),pos[i]=j;}}int main(){scanf("%s%s",s+1,t+1);n=strlen(s+1),m=strlen(t+1);init();KMP();for(int i=1;i<=n;++i)if(!vis[i]) printf("%c",s[i]);return 0;}

免责声明：本网信息来自于互联网，目的在于传递更多信息，并不代表本网赞同其观点。其原创性以及文中陈述文字和内容未经本站证实，对本文以及其中全部或者部分内容、文字的真实性、完整性、及时性本站不作任何保证或承诺，并请自行核实相关内容。本站不承担此类作品侵权行为的直接责任及连带责任。如若本网有任何内容侵犯您的权益，请及时联系我们，本站将会在24小时内处理完毕。