首页 > 编程语言 >2024年2月18日——KMP算法(未完成

2024年2月18日——KMP算法(未完成

时间:2024-02-20 17:45:14浏览次数:29  
标签:lb la int 18 2024 maxn KMP strlen

点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+10;
int kmp[maxn];
int la,lb,j;
char a[maxn],b[maxn];
int main(){
	cin>>a+1>>b+1;
	la=strlen(a+1),lb=strlen(b+1);
	for(int i=2;i<=lb;i++){
		while(j&&b[j+1]!=b[i]){
			j=kmp[j];
		}
		if(b[j+1]==b[i] ){
			j+=1;
		}
		kmp[i]=j;
	}
	j=0;
	for(int i=1;i<=la;i++){
		while(j&&b[j+1]!=a[i]){
			j=kmp[j];
		}
		if(b[j+1]==a[i]) j+=1;
		if(j==lb){
			cout<<i-j+1<<endl;
			j=kmp[j];
		}
	}
	for(int i=1;i<=lb;i++) cout<<kmp[i]<<" ";
	return 0;
}

标签:lb,la,int,18,2024,maxn,KMP,strlen
From: https://www.cnblogs.com/Euan99/p/18019758

相关文章

  • 2024.2
    一些以前遗留的题如果想起来了也写进这吧,总归要整理的。ARC171B.Chmax600分的ARCB确实有点难度。先理清操作的实际含义:建出\(i\rightarrowp_i\)的置换环结构,在置换环上从点\(i\)开始走,当下一个点的编号大于自身的时候就走,否则就停下来。然后\(B_i\)就代表最后停留......
  • Codeforces 1806E Tree Master
    考虑一个最基础的暴力,就是直接记忆化搜索暴力往上跳。但是能发现如果一层的节点数过多,状态数太多,就寄了。再考虑一个基础的暴力,就是直接跳。但是如果要跳的层数过多,就寄了。考虑结合一下,根号分治。对于一层内节点数\(\le\sqrt{n}\)的记录下每两个点间的答案。对于节点数......
  • CF1893B Neutral Tonality 题解
    很巧妙的一道题。为了让\(\text{LIS}\)长度最小,我们肯定先将\(b\)数组降序排序,这样\(b\)自身对\(\text{LIS}\)的贡献最小。考虑是否存在一种插入方式使得最终\(a\)的\(\text{LIS}\)长度和最初\(a\)的\(\text{LIS}\)长度相等。这时我们会发现,如果我们插入\(b\)......
  • 2024牛客寒假算法基础集训营4
    A.直接计算#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongconstintN=1e5+10;#defineinf0x3f3f3f3fvoidsolve(){inta,b,k;cin>>a>>b>>k;if(a>=k*b)cout<<"good";elsecout<&l......
  • CentOS7安装nodejs18
    CentOS7安装nodejs18及以上版本会报错,glibc版本过低。升级glibc到2.28。查看glibc版本号#ldd--version1、下载glibc2.28并创建build目录cdwgethttp://ftp.gnu.org/gnu/glibc/glibc-2.28.tar.gztarxfglibc-2.28.tar.gzcdglibc-2.28/mkdirbuild2、升级gccyuminstall-y......
  • 2024.2 模拟赛日志
    题解一篇没写,就是记录一下分数。WC2024(20240201)\(100+44+5=149\)。T1时间:120min。SS240217(20240217)\(60+10+10=80\)。T160分时间:180min。SS240218(20240218)\(100+20+0=120\)。T1时间:180min。SS240219(20240219)\(100+40+40=180\)。T1时间:180min。USACO24......
  • 2024-02-20 随机生成30位字符串
    functiongenerateRandomString(){letspecialChars="`~!@#$%^&*-+=_|{}[]:;'<>,.?/";letlowercaseLetters='abcdefghijklmnopqrstuvwxyz';letuppercaseLetters='ABCDEFGHIJKLMNOPQRSTUVWXYZ';let......
  • 2024-02-19-物联网C语言(9-链表)
    9.链表9.1概念假如:做一个班级信息管理系统,统计班级学生的信息而我们事先不知道班级人数,或者知道人数,但是中间人员可能发生变化:比如有新同学加入,有同学请假,又或者我们需要统计班级的平均成绩等等目标:要做一个类似QQ、飞秋类似的通信软件,其中有一个功能,类似用户上下线检测、......
  • 2024全年放假日历表及调休安排 用手机便签设置放假倒计时
    对于绝大多数的上班族来说,春节长假已经结束,现在要回归到正常的工作和生活中。为了给生活增加一些“盼头”,很多小伙伴不约而同打开手机日历,查看下个法定节假日是什么时候。下面给大家具体讲一下2024全年放假日历表及调休安排!除去元旦、春节之外,清明节是4月4日至6日放假共3天,4月7日......
  • react 备忘.md.18022871
    useStateuseState是React中一个基本的钩子(Hook),用于在函数组件中添加状态。这个钩子让你能够在不编写类组件的情况下保持组件的内部状态。useCallbackuseCallback是React的一个钩子(Hook),它返回一个记忆化(memoized)的回调函数。这个钩子在某些场景下非常有用,特别是当你需要传......