模板四十天之一 KMP

ゝ一世哀愁。 2021-12-05 00:57 173阅读 0赞

## 题目描述 ##

如题，给出两个字符串s1和s2，其中s2为s1的子串，求出s2在s1中所有出现的位置。

**为了减少骗分的情况，接下来还要输出子串的前缀数组next。**

（如果你不知道这是什么意思也不要问，去百度搜\[kmp算法\]学习一下就知道了。）

## 输入输出格式 ##

**输入格式：**

第一行为一个字符串，即为s1

第二行为一个字符串，即为s2

**输出格式：**

若干行，每行包含一个整数，表示s2在s1中出现的位置

接下来1行，包括length(s2)个整数，表示前缀数组next\[i\]的值。

## 输入输出样例 ##

**输入样例\#1：** 复制

ABABABC
    ABA

**输出样例\#1：** 复制

1
    3
    0 0 1

## 说明 ##

时空限制：1000ms,128M

数据规模：

设s1长度为N，s2长度为M

对于30%的数据：N<=15，M<=5

对于70%的数据：N<=10000，M<=100

对于100%的数据：N<=1000000，M<=1000000

#include<bits/stdc++.h>
    using namespace std;
    int next[1000000];
    void getnext(char p[]){
    	int len=strlen(p);
    	next[0]=-1;
    	int k=-1;
    	int j=0;
    	while(j<len-1){
    		if(k==-1||p[j]==p[k]){//如果为初始值，k在前  j在后  jk是相等的  
    			j++;
    			k++;
    			next[j]=k; 
    		 }else{
    		 	k=next[k];
    		 }
    	}//字符串算法，好像就是向前匹配 
    }
    void getnextval(char p[]){//求next代码优化
    	int len=strlen(p); 
    	next[0]=-1;
    	int k=-1,j=0;
    	while(j<len-1){
    		if(k==-1||p[k]==p[j]){
    			k++;j++;
    			if(p[j]!=p[k])next[j]=k;
    			else next[j]=next[k];
    		}else{
    			k=next[k];
    		}
    	}
    }//优化后的kmp数组 
    
    void kmpsearch(char s[],char p[]){  
    	int lens=strlen(s),lenp=strlen(p),i=0,j=0;
    	while(i<lens){
    		if(j==-1||s[i]==p[j]){
    			i++;
    			j++;
    			if(j==lenp){
    				printf("%d\n",i-j+1);
    				i=i-j+1;
    				j=0;
    			}//每当找到一个起点 
    		}else{
    			j=next[j];
    		}
    	}		
    }
    int main(){
    	char s[10000],p[10000];
    	scanf("%s",s);
    	scanf("%s",p);
    	getnextval(p);
    	kmpsearch(s,p);
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，173人围观）

还没有评论，来说两句吧...

相关阅读

相关扩展kmp 模板

题目描述有两个字符串aa,bb,要求输出bb与aa的每一个后缀的最长公共前缀输入格式两行,分别为两个字符串aa,bb 输出格式共两行第一行有l

ゞ浴缸里的玫瑰/ 2023年06月07日 12:14/ 0 赞/ 15 阅读

相关 KMP模板

include <stdio.h> void getnext(char ch, int next[]); int kmp(char ch1,

末蓝、/ 2022年09月20日 15:13/ 0 赞/ 179 阅读

相关 KMP模板

KMP算法是快速字符串匹配算法，朴素的暴力算法的时间复杂度为O（n\m），而KMP通过对模式串进行相应的处理，能够达到O（m+n）的速度。我们知道在字符串匹配的时候最消耗时

我不是女神ヾ/ 2022年08月10日 16:34/ 0 赞/ 178 阅读

相关 KMP模板

/ pku3461(Oulipo), hdu1711(Number Sequence) 这个模板字符串是从0开始的 Next数组是从1开始的

╰+哭是因爲堅強的太久メ/ 2022年05月30日 06:24/ 0 赞/ 156 阅读

相关 Qt第二十四天

绘制动态曲线 ifndef MAINWINDOW_H define MAINWINDOW_H include <QMainWind

迷南。/ 2022年04月02日 13:49/ 0 赞/ 317 阅读

相关第三十四天

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][] from threading import Thread

本是古典何须时尚/ 2022年01月05日 14:31/ 0 赞/ 284 阅读

相关 KMP模板

1 include <iostream> 2 include <string> 3 using namespace std; 4 / P

╰+攻爆jí腚メ/ 2021年12月20日 23:57/ 0 赞/ 210 阅读

相关模板四十天之一 KMP

题目描述如题，给出两个字符串s1和s2，其中s2为s1的子串，求出s2在s1中所有出现的位置。为了减少骗分的情况，接下来还要输出子串的前缀数组next。（如果你

ゝ一世哀愁。/ 2021年12月05日 00:57/ 0 赞/ 174 阅读

相关模板四十天之笛卡尔树

笛卡尔树：简介 Cartesian Tree 是一种二叉树，每个节点具有两个值 key 和 value。只看key的话，笛卡尔树是一棵二叉搜索树只看va

左手的ㄟ右手/ 2021年12月01日 11:24/ 0 赞/ 280 阅读

相关第十四天

今日所得　　模块　　import 　　from...import... 　　循环导入　　相对导入　　绝对导入　　软件开发目录规范模块　　模块：是

拼搏现实的明天。/ 2021年11月11日 09:10/ 0 赞/ 373 阅读