奥赛一本通 1470 Censoring

1470 Censoring题目大意给出两个字符串 S 和 T每次从前往后找到 S 的子串 T 并将其删除空位向前补齐直到 S 串中不含 T 串。一本通题面有误知识要点KMP解题思路在使用 KMP 算法匹配时一边扫描字符串 S 一边将其入栈当发现找到 T 时则从栈顶取出相应数量的字符此时指向 T 的指针就应该回退到扫描栈顶字符时的位置然后继续匹配。因此需要使用一个数组记录栈中每个字符对应的 T 串中的指针。参考代码#includebits/stdc.husingnamespacestd;constintN1000005;chars[N],t[N];intf[N],pos[N];intmain(){scanf(%s%s,s,t);intmstrlen(s),nstrlen(t),k0;for(inti1,j0;in;i){while(jt[i]!t[j])jf[j-1];if(t[i]t[j])j;f[i]j;}for(inti0,j0;im;i,k){while(js[i]!t[j])jf[j-1];if(s[i]t[j])j;s[k]s[i],pos[k]j;//扫描过的字符就地存储同时记录对应的 jif(jn)k-n,jpos[k];//移除栈顶字符指针 j 回退}s[k]0,puts(s);return0;}