http://acm.hdu.edu.cn/showproblem.php?pid=1686
题意:求模式串在主串中出现的次数【可重叠】
Sample Input
3
BAPC
BAPC
AZA
AZAZAZA
VERDI
AVERDXIVYERDIAN
Sample Output
1
3
0
跟这个有相同点的题:http://972169909-qq-com.iteye.com/blog/1071548#
对代码中神奇的地方进行解释:
那么3的意义可以表示为
可见next[len2]的意义:前缀和后缀的最长匹配长度
现在就以这个为模式串模拟一下: |
主串: A B A B A B C A B A B A A B |
|
模式串: A B A B C A B A |
匹配成功后下一步的情况应为: |
主串: A B A B A B C A B A B A A B |
|
模式串: A B A B C A B A |
指针直接移动到红色部分进行匹配 |
如何理解呢?
我们先不看最后那4个字符"BAAB",就可以发现最大前缀【指前缀和后缀的最长匹配长度】直接挪动到最大后缀那里了,为什么可以这样呢?因为前面都是显然不能够匹配成功的
可以向前移动一位试试看:
主串: A B A B A B C A B A B A A B |
|
模式串: A B A B C A B A |
我们先不看最后那4个字符"BAAB",可以看到现在是4长度的前缀与4长度的后缀比较,显然不 |
可匹配,因为最大匹配长度是3【指前缀和后缀的最长匹配长度】,显然再向前移也不行的 |
第一次长篇大论,若有错误或不明白之处,请指出
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <algorithm>
using namespace std;
#define L1 1000005
#define L2 10005
int next[L2], len1, len2, res;
char s[L1], p[L2];
void get_next ()
{
int j = 0, k = -1;
next[0] = -1;
while (j < len2)
{
if (k == -1 || p[j] == p[k])
{
j++, k++;
next[j] = k;
}
else k = next[k];
}
}
void kmp (int pos)
{
int i = pos, j = 0;
while (i < len1 && j < len2)
{
if (j == -1 || s[i] == p[j])
{
i++, j++;
}
else j = next[j];
if (j >= len2)
res++, j = next[j]; //神奇之处,效率大增
}
}
int main()
{
int t;
scanf ("%d", &t);
while (t--)
{
res = 0;
scanf ("%s%s", p, s);
len1 = strlen (s);
len2 = strlen (p);
get_next ();
kmp (0);
printf ("%d\n", res);
}
return 0;
}
- 大小: 23.4 KB
- 大小: 20.6 KB
分享到:
相关推荐
【标题】"HDU_2010.rar"是一个压缩包文件,其中包含了与"HDU 2010"相关的资源,特别是针对"HDU ACM20"比赛的编程题目。"hdu 2010"和"hdu 20"可能是该比赛的不同简称或分类,而"hdu acm20"可能指的是该赛事的第20届...
HDU(杭州电子科技大学在线评测系统)是一个深受程序员喜爱的在线编程练习平台,它提供了丰富的算法题目供用户挑战,帮助他们提升编程技能和算法理解能力。"hdu.rar_hdu"这个压缩包文件很可能是某位程序员整理的他在...
【标题】"HDU题目java实现"所涉及的知识点主要集中在使用Java编程语言解决杭州电子科技大学(HDU)在线评测系统中的算法问题。HDU是一个知名的在线编程竞赛平台,它提供了大量的算法题目供参赛者练习和提交解决方案...
ACM HDU 题目分类 ACM HDU 题目分类是指对 HDU 在线判题系统中题目的分类,总结了大约十来个分类。这些分类将有助于编程选手更好地理解和解决问题。 DP 问题 DP(Dynamic Programming,动态规划)是一种非常重要...
### hdu1250高精度加法 #### 背景介绍 在计算机科学与编程竞赛中,处理大整数运算(特别是加法、减法、乘法等)是常见的需求之一。当数字的位数超过了标准数据类型(如`int`、`long`等)所能表示的最大值时,就需要...
【标题】"hdu.rar_HDU 1089.cpp_OJ题求和_hdu_horsekw5_杭电obj" 提供的信息是关于一个压缩文件,其中包含了一个名为 "HDU 1089.cpp" 的源代码文件,这个文件是为了解决杭州电子科技大学(Hangzhou Dianzi ...
【标题】"HDU DP动态规划"涉及到的是在算法领域中的动态规划(Dynamic Programming,简称DP)技术,这是解决复杂问题的一种高效方法,尤其适用于有重叠子问题和最优子结构的问题。动态规划通常用于优化多阶段决策...
HDU1059的代码
hdu1001解题报告
hdu 1574 passed sorce
【标题】"HDU.rar_hdu_hdu07_com_shownv9b_www.563hdu." 暗示这是一个与HDU(杭州电子科技大学在线编程平台)相关的压缩包,其中可能包含了该平台上的编程竞赛题目或练习题目的源代码。"hdu07"可能是某个特定题目的...
【ACM HDU】指的是在ACM(国际大学生程序设计竞赛,International Collegiate Programming Contest)中,参赛者在杭州电子科技大学(Hangzhou Dianzi University,简称HDU)的在线评测系统上完成并已解决的题目集合...
【标题】"hdu_acm_1084.rar_ACM_HDU10_acm10_hdu_hdu 1084" 提供的是一个关于杭电(HDU)ACM竞赛第1084题的解决方案。该题目可能是在编程竞赛中常见的算法问题,而ACM(国际大学生程序设计竞赛)是全球知名的编程...
【标题】:杭电ACMhdu1163 【描述】:这是一道源自杭州电子科技大学(Hangzhou Dianzi University,简称HDU)的ACM编程竞赛题目,编号为1163。这类问题通常需要参赛者利用计算机编程解决数学、逻辑或算法上的挑战,...
HDU是杭州电子科技大学(Hangzhou Dianzi University)举办的一个在线编程竞赛平台,全称为HDU Online Judge。ACM是国际大学生程序设计竞赛(International Collegiate Programming Contest)的缩写,是一个全球性的...
hdu2101AC代码
【ACM入门与提高:HDU ACM竞赛课程详解】 ACM(国际大学生程序设计竞赛,International Collegiate Programming Contest,简称ICPC或ACM/ICPC)是一项全球性的竞赛,旨在激发大学生对计算机科学的兴趣,提升他们的...
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
HDU(Hangzhou Dianzi University)是国内外知名的在线编程竞赛平台,主要服务于ACM/ICPC(国际大学生程序设计竞赛)以及相关的算法训练。"HDU最全ac代码"这个压缩包很可能是包含了在HDU平台上解题通过的完整源代码...
根据提供的信息,我们可以总结出以下关于“hdu动态规划算法集锦”的知识点: ### 动态规划基础概念 动态规划是一种解决多阶段决策问题的方法,它通过将原问题分解为互相重叠的子问题,利用子问题的解来构建原问题...