Smiling & Weeping
---- 我只为你一个人写过月亮
题目链接:P4824 [USACO15FEB] Censoring S - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
题目思路:编码时,在正常的kmp中加入以下两条:
1.定义一个和S一样大的数组记录每个字符对应的j值,用于删除一个P后j回到P前面的值,还应该有一个记录该位字符是不是被删除过,以防以后回溯又重新计算
2.用一个栈记录删除P的后的结果。每一次移动i就把S[i]入栈,若kmp匹配到一个P,此时栈顶的几个字符就是P,把栈顶的P弹出,相当于删除这个P。最后栈中留下的就是S中删除了所有P的结果
Talk is cheap , show me the code
1 #include<bits/stdc++.h> 2 // 注意不一定是ind-plen,因为这个地方可能被删除过 3 using namespace std; 4 int n , Next[2000100] , t[2000100]; 5 bool ff[2000100]; 6 char str[2000100] , pattern[2000100] , ans[2000100]; 7 stack<char> st; 8 void getNext(char *p , int plen){ 9 Next[0] = 0; Next[1] = 0; 10 for(int i = 1; i < plen; i++){ 11 int j = Next[i]; 12 while(j && p[i] != p[j]) 13 j = Next[j]; 14 if(p[i] == p[j]) Next[i+1] = j+1; 15 else Next[i+1] = 0; 16 } 17 } 18 void kmp(char *s , char *p){ 19 int ind=0; 20 bool flag = true; 21 int slen = strlen(s) , plen = strlen(p); 22 getNext(p , plen); 23 int j = 0; 24 for(int i = 0; i < slen; i++){ 25 st.push(s[i]); 26 if(s[i] != p[j]) flag = true; 27 while(j && s[i] != p[j]){ 28 j = Next[j]; 29 } 30 if(s[i] == p[j]) j++; 31 t[i] = j; 32 if(j == plen){ 33 int cnt = 0 , inde = i; 34 while(cnt != plen){ 35 if(!ff[inde]) ff[inde] = true , cnt++; 36 inde--; 37 } 38 if(flag) ind = i , flag = false; 39 int tem = plen , fff = ind-plen; 40 while(ff[fff]) fff--; 41 j = t[fff]; 42 ind -= j; 43 while(tem--) 44 st.pop(); 45 } 46 } 47 } 48 int main() 49 { 50 scanf("%s",str); 51 scanf("%s",pattern); 52 kmp(str , pattern); 53 int len=st.size(); 54 while(!st.empty()) 55 ans[--len] = st.top() , st.pop(); 56 printf("%s",ans); 57 return 0; 58 }
不愿勾起相思,不敢出门看月。
偏偏月仅窗来,害我一夜相思。
文章到此结束我们下次再见(* ̄︶ ̄)
标签:int,kmp,Next,while,应用,简单,plen,st From: https://www.cnblogs.com/smiling-weeping-zhr/p/17684517.html