KMP算法之入门例题：剪布条

我就是我 2022-02-23 08:44 84阅读 0赞

题目：[http://acm.hdu.edu.cn/showproblem.php?pid=2087][http_acm.hdu.edu.cn_showproblem.php_pid_2087]

题目大意 ：给两个串，看第二个串在第一个串中出现多少次

思路：一般kmp的做法在str2匹配完后就他跳出循环，这时候把跳出循环改成str2从头继续匹配即可。

#include<bits/stdc++.h>
    using namespace std;
    char T[100000],t[100000];
    int nex[100000],res=0,ans=0; 
    void getnext(){
    	int len=strlen(t);
    	int j=0,k=-1;
    	nex[0]=-1;
    	while(j<len)
    		if(k==-1||t[j]==t[k])nex[++j]=++k;//如果匹配成功  next的下一个就等于匹配成功的下一个 
    		else k=nex[k]; //匹配失败不断寻找有相同前缀的 
    }
    void solved(){
    	int lenT=strlen(T);
    	int lent=strlen(t);
    	int i=0,j=0;
    	res=ans=0;
    	while(i<lenT&&j<lent){
    		if(j==-1||T[i]==t[j]){
    			i++;j++;
    		}else j=nex[j];
    		if(j==lent){
    			res++;j=0;
    		}
    	}
    }
    int main(){
    	scanf("%s",T);
    	while(T[0]!='#'){
    		scanf("%s",t);
    		getnext();
    		solved();
    		printf("%d\n",res);	
    		scanf("%s",T);	
    	}
    	return 0;
    }

[http_acm.hdu.edu.cn_showproblem.php_pid_2087]: http://acm.hdu.edu.cn/showproblem.php?pid=2087

发表评论取消回复

表情：

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

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

相关阅读

相关 HDU 2087 剪花布条（KMP算法）

剪花布条 Problem Description 一块花布条，里面有些图案，另有一块直接可用的小饰条，里面也有一些图案。对于给定的花布条和小饰条，计算一下能从

超、凢脫俗/ 2024年02月17日 21:12/ 0 赞/ 18 阅读

相关递归算法及例题入门

[全文参考自bilibili作者连烟][bilibili] [算法笔记总目录][Link 1] 一、概述 1 . 概念编程语言中，函数Func(Type

野性酷女/ 2023年02月18日 01:48/ 0 赞/ 81 阅读

相关数据结构笔记----KMP算法例题求解next数组

已知模式T="abaabcaba”,求其对应的next\[0..8\]的值。 ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10

野性酷女/ 2023年01月03日 12:48/ 0 赞/ 145 阅读

相关 hdu2087剪花布条（kmp）

剪花布条 Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Othe

朱雀/ 2022年08月21日 08:59/ 0 赞/ 116 阅读

相关 KMP算法入门详解

最近学KMP算法。。看了好多博客都没太看懂，然后发现一篇写得很好的博客，转载下来慢慢看慢慢学本文转载自：[http://www.cnblogs.com/c-cloud/p/

雨点打透心脏的1/2处/ 2022年06月10日 13:23/ 0 赞/ 158 阅读

相关 Hdu 2087 剪花布条(KMP基础)

[传送门][Link 1] 题意：给你两个字符串问你其中一个字符串在另一个字符串中出现了几次。分析：这题显然用KMP做，不然很容易超时，其实这基本算是一个KMP模板题，如

谁践踏了优雅/ 2022年05月19日 06:58/ 0 赞/ 132 阅读

相关 HDU 2087 剪花布条 KMP入门

Problem Description 一块花布条，里面有些图案，另有一块直接可用的小饰条，里面也有一些图案。对于给定的花布条和小饰条。计算一下能从花布条中尽可能剪出几块小饰

青旅半醒/ 2022年03月30日 04:58/ 0 赞/ 162 阅读

相关 KMP算法之入门例题：剪布条

题目：[http://acm.hdu.edu.cn/showproblem.php?pid=2087][http_acm.hdu.edu.cn_showproblem.php_

我就是我/ 2022年02月23日 08:44/ 0 赞/ 85 阅读

相关 hdu 2087 剪花布条 KMP

题目链接：[http://acm.hdu.edu.cn/showproblem.php?pid=2087][http_acm.hdu.edu.cn_showproblem.ph

小灰灰/ 2021年12月09日 15:41/ 0 赞/ 188 阅读

相关字符串之KMP算法

一、介绍　　KMP算法全称Knuth-Morris-Pratt算法，是一种字符串匹配算法，常规字符匹配是每次移动一位，复杂度O(mn)；而KMP算法复杂度O(m+n)。

谁借莪１个温暖的怀抱￠/ 2021年09月11日 01:54/ 0 赞/ 390 阅读