首页 > 其他分享 >kmp模板

kmp模板

时间:2023-09-07 12:22:24浏览次数:37  
标签:cnt int Next kmp plen include 模板

Smiling & Weeping

               ---- 深情是我担不起的重任,情话只是偶然兑现的谎言

 

题目:Problem - 2087 (hdu.edu.cn)

就是简单的kmp,再加上一个判断是否和上一个重复

现在上模板:

Talk is cheap , show me the code

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cmath>
 4 #include<cstdio>
 5 #include<algorithm>
 6 using namespace std;
 7 char str[2010] , pattern[2010];
 8 int Next[2010];
 9 int cnt;
10 void getNext(char *p , int plen){           // 计算Next[1]~Next[plen]
11     Next[0] = 0; Next[1] = 0;
12     for(int i = 1; i < plen; i++){          // 把i的增加看作后缀的逐步扩展
13         int j = Next[i];                    // j的后移:j指向前缀阴影w的后一个字符
14         while(j && p[i] != p[j])            // 阴影的后一个字符不相同
15             j = Next[j];                    // 更新j
16         if(p[i] == p[j]) Next[i+1] = j+1;
17         else    Next[i] = 0;
18     }
19 }
20 void kmp(char *s , char *p){
21     int last = -1;
22     int slen = strlen(s) , plen = strlen(p);
23     getNext(p , plen);                          // 预计算Next[]数组
24     int j = 0;
25     for(int i = 0; i < slen; i++){              // 匹配s和p的每个字符
26         while(j && s[i] != p[j])                // 失配了
27             j = Next[j];                        // j滑动到Next[j]位置
28         if(s[i] == p[j]) j++;                   // 当前位置匹配,继续
29         if(j == plen){                          // j到了p的末尾,找到了一个匹配
30             if(i-last >= plen){                 // 判断新的匹配和上一个匹配是否能分开
31                 cnt++;
32                 last=i;
33             }
34         }
35     }
36 }
37 int main()
38 {
39     while(~scanf("%s",str)){
40         if(str[0] == '#') break;
41         scanf("%s",pattern);
42         cnt = 0;
43         kmp(str , pattern);
44         printf("%d\n",cnt);
45     }
46     return 0;
47 }

我是一只决心不再躲闪的鸟

文章到此结束,我们下次再见o(╥﹏╥)o

标签:cnt,int,Next,kmp,plen,include,模板
From: https://www.cnblogs.com/smiling-weeping-zhr/p/17684497.html

相关文章

  • Vue源码学习(二):<templete>渲染第一步,模板解析
    好家伙, 1.<template>去哪了在正式内容之前,我们来思考一个问题,当我们使用vue开发页面时,<tamplete>中的内容是如何变成我们网页中的内容的? 它会经历四步:解析模板:Vue会解析<template>中的内容,识别出其中的指令、插值表达式({{}}),以及其他元素和属性。生成AST:解析模......
  • pageoffice模板套红
    转载:模板套红模板套红注意本文中展示的代码均为关键代码,复制粘贴到您的项目中,按照实际的情况,例如文档路径,用户名等做适当修改即可使用。在Web项目中处理Word文档,经常会用到Word模板,只不过这里的“模板”概念,都是指在Web项目中预先放置的doc、docx等扩展名的、真正的Word文档,对......
  • 使用 vue 渲染静态模板
    最近再一次需要做纯静态页面(无任何脚本语言,只保留css和html),以往我直接使用ejs生成,但是工作中一直使用jsx和vue来组装页面,就突发奇想,难道react、vue不能只渲染纯静态页面吗?有了这个想法,我就想验证下可行性,万能百度开始,找了一圈,发现基本都是需要脚本依赖的,这就意味着必......
  • 金蝶云星空创建带分录的业务单据模板(协同开发云)
     业务对象的创建方式有新建、复制、继承三种:新建:基于空白对象创建,不受任何约束,灵活度高,元素、菜单都需要自行添加。常用于动态表单、移动业务的开发。复制:原对象复制出新的业务对象,对原对象与新对象的改动不会相互影响。常用于动态表单、移动业务的开发。继承:继承原对象的元......
  • 模板字符串
    点击查看代码functionrender(template,data){constreg=/\{\{(\w+)\}\}/;//模板字符串正则if(reg.test(template)){//判断模板⾥是否有模板字符串constname=reg.exec(template)[1];//查找当前模板⾥第⼀个模板字符串的字段template=template.replace(reg,......
  • flask设置静态文件目录、模板目录
    fromflaskimportFlask,render_templateapp=Flask(import_name=__name__,static_url_path='/',static_folder='static',template_folder='templates')#添加html访问路由@app.route('/')defblog():retur......
  • STL标准模板之容器
    一、vector向量容器头文件:#include<vector>采用顺序结构存储数据,可以使用下标进行随机访问,有时候也叫数组容器(C++11中增加了array容器,定长数组容器,相比普通数组它是类类型,增加成员函数,提高安全性)vector是可变长的顺序表结构,可以自动扩容,容器中的元素存储在连续内存,支......
  • Vue-----模板插值-----(v-once、v-html、v-bind使用)
    1、v-once当组件在进行变量插值时只会插值一次。某些情况下,某些组件的渲染是由变量控制的,但是我们想让它一旦渲染后就不能够再被修改,可以是由v-once来实现<!DOCTYPEhtml><htmllang="en"><head><metacharset="UTF-8"><metaname="viewport"content="widt......
  • C#中单例模板
    泛型单例/***泛型单例模板where限制这个单例类必须要能被new出来*/publicclassSingleton<T>:IDisposablewhereT:new(){privatestaticTinstance;publicstaticTInstance{get{if(instance==null)instance=new......
  • 洛谷P3808 【模板】AC 自动机(简单版)题解 AC自动机模板题
    题目链接:https://www.luogu.com.cn/problem/P3808AC自动机模板题。示例程序:#include<bits/stdc++.h>usingnamespacestd;constintmaxn=1e6+5;structNode{intson[26],fail,id;Node(){}Node(int_id){memset(son,0,sizeof(son));......