专栏首页Zaqdt_ACMHDU 2087 剪花布条(裸KMP)

HDU 2087 剪花布条(裸KMP)

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

本文链接:https://blog.csdn.net/Charles_Zaqdt/article/details/102543718

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2087

写法就是一个裸的KMP,只不过是每次再匹配了一次以后,让j=0(让其从第一个开始匹配)


AC代码:

#include <bits/stdc++.h>
#define maxn 1005
#define ll long long
using namespace std;
string s, p;
int Next[maxn];
int ans;

void init(){
	int j = 0, k = -1;
	int len = p.length();
	memset(Next, -1, sizeof(Next));
	while(j < len){
		if(k == -1 || p[j] == p[k]){
			k ++;
			j ++;
			Next[j] = k;
		}
		else k = Next[k];
	}
}

void kmp(){
	int i = 0, j = 0;
	int l1 = s.length();
	int l2 = p.length();
	while(i < l1){
		if(j == -1 || s[i] == p[j]){
			i ++;
			j ++;
		}
		else{
			j = Next[j];
		}
		if(j == l2){
			j = 0;
			ans ++;
		}
	}
}

int main()
{
	while(cin>>s){
		if(s == "#") break;
		cin>>p;
		init();
		ans = 0;
		kmp();
		printf("%d\n", ans);
	}
	return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • HDU 1686 Oulipo(KMP)

    题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1686

    Ch_Zaqdt
  • NYOJ 32 组合数(dfs递归)

    Ch_Zaqdt
  • POJ 3020 Antenna Placement(二分图最小边覆盖)

           题意是有一个n*m的地图,图中'*'表示城市,现在要给每个城市覆盖无线,需要安装基站,每个基站最多只能覆盖相邻的两个城市,也就是1*2或者2*1的...

    Ch_Zaqdt
  • HDU 1686 Oulipo(KMP)

    题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1686

    Ch_Zaqdt
  • P2782 友好城市

    题目背景 无 题目描述 有一条横贯东西的大河,河有笔直的南北两岸,岸上各有位置各不相同的N个城市。北岸的每个城市有且仅有一个友好城市在南岸,而且不同城市的友好城...

    attack
  • 通过代码定义shape/selector

    六月的雨
  • 5709 01背包

    5709 01背包  时间限制: 1 s  空间限制: 128000 KB  题目等级 : 黄金 Gold 题解  查看运行结果 题目描述 Descriptio...

    attack
  • 2015年javaB组1-4题解析与理解

    X老板脾气古怪,他们公司的电话分机号都是3位数,老板规定,所有号码必须是降序排列,且不能有重复的数位。比如:

    萌萌哒的瓤瓤
  • 第八届蓝桥杯省赛javaB组题目解析

    作者自己做完之后发现省赛的一幕其实是不难的,说实话,自己觉得题目难度还没有PAT甲级的难度高。 而且作者做了这么些天之后发现了,PAT甲级主要喜欢考数据结构方...

    萌萌哒的瓤瓤
  • 《C++那些事》项目概要及一文彻底搞懂C和C++中struct

    最近一直在更新一个仓库:《C++那些事》,将自己学习的难点与重点罗列进去,并配上相关代码,实践与理论结合。

    公众号guangcity

扫码关注云+社区

领取腾讯云代金券