首页 > 其他分享 >kmp的简单应用

kmp的简单应用

时间:2023-09-07 12:57:58浏览次数:33  
标签:int kmp Next while 应用 简单 plen st

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

相关文章

  • 拓展kmp
    Smiling&Weeping----我从不觉得暗恋是苦涩的,对一个人的喜欢藏在眼睛里,透过它,世界都变得更好看了。题目:P5410......
  • 5G时代下,如何解决视频业务应用之间视频能力的融合问题?
    5G时代下,如何解决视频业务应用之间视频能力的融合问题?5G时代下,5G网络的低延迟、高速率和广覆盖性加快了各行业领域的智能化速度,同时促进了“万物互联”生态系统的建设,而视频信息也成为各领域智能化发展的可视化载体与管理途径。面向复杂而互联的多领域市场,视频业务呈现出行业化、场......
  • kmp模板
    Smiling&Weeping----深情是我担不起的重任,情话只是偶然兑现的谎言 题目:Problem-2087(hdu.edu.cn)就是简单的kmp,再加上一个判断是否和上一个重复现在上模板:Talkischeap,showmethecode1#include<iostream>2#include<cstr......
  • DeeTune:基于 eBPF 的百度网络框架设计与应用
    作者|百度APP云原生技术研发组导读随着云计算的技术的不断迭代演进,百度内部服务逐渐搬迁到云环境中,部署成本和效率取得明显收益,但一些可观测能力的短板和缺失逐渐显露,传统的方式往往通过植入代码进行修改来实现,但在业务形态和技术栈多样性的背景下,面临业务被侵入、沟通协调、性能......
  • 句柄的概念及简单运用
    在计算机编程中,句柄(Handle)通常是一个整数或其他数据类型的值,用于标识或引用对象、资源或数据结构的引用。句柄通常被用来管理和操作系统级别的资源,例如文件、内存、图形界面窗口、设备上下文等等。句柄是一种抽象的数据类型,它允许程序在需要的时候引用和操作底层资源,而不必了解底层......
  • Python爬虫在SEO中的应用及其效果分析
    随着互联网的快速发展,搜索引擎优化(SEO)成为了网站提高可见性和流量的重要策略。而Python爬虫作为一种强大的网络数据抓取工具,为SEO提供了许多便利和优势。今天我们将探讨Python爬虫在SEO中的应用,并进行一些简单的效果分析,帮助大家深入了解这项技术的潜力和价值。首先,我们必须要了解P......
  • Web应用防火墙--规则防护
    一、什么是Web应用防火墙?Web应用防火墙对网站、APP的业务流量安全及合规性保护,对业务流量的识别恶意特征提取、分析识别出恶意流量并进行处理,将正常安全的流量回源到业务服务器,保护网站核心业务和数据安全。京东云Web应用防火墙的产品架构示意图如下:二、Web攻击常见的检测手......
  • js简单日历制作
    简易的效果图:废话不多说,直接代码:<!DOCTYPEhtml><htmllang="en"><head><metacharset="UTF-8"><metahttp-equiv="X-UA-Compatible"content="IE=edge"><metaname="viewport"co......
  • clickhouse的简单介绍及使用
    转:https://blog.csdn.net/qq_44275894/article/details/123973699一、介绍cliskhouse官方地址ClickHouse是一个真正的面向列的数据库管理系统(DBMS),用于查询的在线分析处理(OLAP)。数据按列存储,并且在执行数组(向量或列块)期间存储。只要有可能,操作就会被发送到数组上,而不是单......
  • PYTHON 简单的网页图片爬虫
    直接上代码:'''简单的网页图片爬虫要先安装requests,BeautifulSoup的库pipinstallrequestspipinstallbs4是一个可以从HTML或XML文件中提取数据的Python库pipinstalllxml'''importrequests#导入requests库frombs4importBeautifulSoupdefget_htmls(p......