首页 > 其他分享 >Censoring S

Censoring S

时间:2024-01-24 14:56:36浏览次数:27  
标签:字符 删除 队列 双端 Censoring KMP

利用KMP和双端队列

这一道题目中间会删除字符,考虑到这种动态的过程我们一般会用链表,栈或者队列维护

这里为了方便最后的输出用双端队列

考虑KMP的过程,他其实对字符串是不是在连续的一个存储空间里并没有要求,也就是说,如果我们给了一堆字符,即使不是按照字符数组那种放在连续的存储空间里面,只要我们知道了每一个字符的\(next\)数组,我们就可以递推下去(因为KMP不要求高效率访问某一个字符)

具体来说,假设双端队列里面存放的是还未删除的字符,对于一个新加入的字符,用KMP相同的过程跑一次,如果长度达到要求直接删除就好

如果不太清楚上面说什么直接看洛谷的代码,很easy可以看懂

标签:字符,删除,队列,双端,Censoring,KMP
From: https://www.cnblogs.com/dingxingdi/p/17984671

相关文章

  • P4824 [USACO15FEB] Censoring S
    P4824[USACO15FEB]CensoringSKMP+栈同样的套路,先找B的最长前后缀,然后与A匹配不同的是要删除A中的B,特殊的是删除之后可能会产生新的B那我们可以利用栈的思想,利用f数组,记录A每一位置上B的匹配程度,这样删除时,直接回到上一个匹配程度,以防漏掉。利用栈记录下标,还在栈内的,说明......
  • 做题记录:P3121 [USACO15FEB] Censoring G
    题目传送门:clickhere题意简化:给定一个文本串,和n个匹配串,删掉文本串中的匹配串求最后的字符串做这题之前应该先做简化版:eazymode上面这题用kmp+栈就能过以前如果用的是\(erase\)函数是错解,字符串的\(erase\)时间复杂度是常数级别的看到这道题后非常的高兴,直接打了个爆力跳......
  • BZOJ 3942: [Usaco2015 Feb]Censoring KMP
    3942:[Usaco2015Feb]CensoringTimeLimit: 10Sec  MemoryLimit: 128MBSubmit: 476  Solved: 260[Submit][Status][Discuss]DescriptionFarmerJohnhaspurchasedasubscriptiontoGoodHooveskeepingmagazineforhiscows,sotheyhaveplentyofmateria......
  • Luogu P4824 [USACO15FEB] Censoring S
    [USACO15FEB]CensoringS题面翻译FarmerJohn为他的奶牛们订阅了GoodHooveskeeping杂志,因此他们在谷仓等待挤奶期间,可以有足够的文章可供阅读。不幸的是,最新一期的文章包含一篇关于如何烹制完美牛排的不恰当的文章,FJ不愿让他的奶牛们看到这些内容。FJ已经根据杂志的所有文字,......
  • P4824 [USACO15FEB] Censoring S
    希望在Str中删掉1个屏蔽词(一个屏蔽词可能出现多次)求最后的串 栈+hash #include<iostream>#include<cstring>usingnamespacestd;constintN=1e6+3;......
  • 关于AC自动机的一些理解 || Luogu3121 & 4824 Censoring - 哈希 - AC自动机
    题目链接:https://www.luogu.com.cn/problem/P3121(4824)题解:4824是CensoringS,只需要对单模式串进行操作,3121需要对多模式串4824开一个前缀hash数组,每次扫到当前点......
  • luoguP4824 [USACO15FEB] Censoring S 解题报告
    血的教训。。。传送门题意FJ已经根据杂志的所有文字,创建了一个字符串$S$($S$的长度保证不超过$10^6$),他想删除其中的子串$T$,他将删去$S$......