传送门:http://acm.hdu.edu.cn/showproblem.php?pid=1711
题意:裸的模式匹配问题,N值较大,必须使用线性算法,考虑上KMP。
关于KMP:
好久之前就看过KMP不过一直没搞懂,最近要搞下字符串,所以先拿它开刀,翻看了严蔚敏老师的数据结构,研究了许久,算是对KMP略知一二了吧,其KMP主算法还是比较好理解来的(不回溯主串匹配指针,当失配时,利用已经匹配的部分串的信息,使模式串指针向前移动,然后继续匹配),关键在于NEXT数组的求法,其实也不算很难理解(一个递推关系+自匹配的过程),书上后面说的那个修正NEXT数组的求法也比较好理解(当P[i]=P[Next[i]]时,此次滑动的没有作用的,所以直接滑到下一次去)。
关于算法的云云就没什么好说的,严蔚敏老师的书说的十分详细。(其实也是自己理解还不够深刻,不能很好的表达出来)
还有要注意一些关于coding方面的技巧。
献上一个使用了修正NEXT数组的KMP模板:
#include<iostream>
using namespace std;
const int MAXN = 1111111,MAXM = 11111;
int T[MAXN],P[MAXM],Next[MAXM];
void MakeNext(int M){
Next[0] = -1;
int i = 0, j = -1;
while(i<M){
if(j==-1||P[i]==P[j]){
i++,j++;
if(P[i]!=P[j])Next[i] = j;
else Next[i] = Next[j];
}
else j = Next[j];
}
}
int KMP(int N,int M){
int i=0,j=0;
while(i<N&&j<M){
if(T[i]==P[j]||j==-1)i++,j++;
else j = Next[j];
}
if(j==M)return i-M+1;
else return -1;
}
int main(){
int N,M,C;
scanf("%d",&C);
while(C--){
scanf("%d%d",&N,&M);
for(int i=0;i<N;i++)scanf("%d",&T[i]);
for(int i=0;i<M;i++)scanf("%d",&P[i]);
if(M>N)printf("-1\n");
else{
MakeNext(M);
printf("%d\n",KMP(N,M));
}
}
return 0;
}
分享到:
相关推荐
HDU-1711 Number Sequence(KMP算法)For each test case, you should output one line wh
next[i]的含义是在str[i]之前的字符串str[0...i]中,必须以str[i-1]结尾的后缀子串(不能包含str[0])与必须以str[0]开头的前
kmp算法,kmp-algorithm-master (1).zip
模式匹配,KMP算法,string-match-kmp-master.zip
kmp算法 KMP算法是一种用于在一个文本串S中查找一个模式串P出现位置的高效算法。KMP算法的核心思想是利用模式串P本身的信息来避免在文本串S中进行不必要的匹配。具体来说,KMP算法通过预处理模式串P,构建一个部分...
kmp算法kmp-algorithm-master.zip
Kernelized Movement Primitives (KMP)-matlab-master.zip
KMP算法(Knuth-Morris-Pratt Algorithm)是一种改进的字符串匹配算法,由D.E.Knuth、J.H.Morris和V.R.Pratt提出。该算法的核心思想是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数,以达到快速匹配的目的...
C语言实现 WIN-TC专用 实现高速关键字查找功能
KMP算法的板子
KMP算法,Martix67大神blog精华剪辑PDF版
KMP算法讲解之——不需要公式-就能理解KMP算法
kmp算法--VC6.0
KMP(Knuth-Morris-Pratt)算法简介及C语言实现 KMP算法,全称Knuth-Morris-Pratt算法,是一种用于在一个主文本字符串(text)中查找一个模式字符串(pattern)的子串的高效算法。KMP算法的核心思想是利用模式字符串的...
acm算法模板之kmp模板,对关键代码做了注释,帮助小白理解
DS串应用--KMP算法DS串应用--KMP算法DS串应用--KMP算法DS串应用--KMP算法
飞行堡垒FX50J无线网卡驱动,安装linux时无法打开wifi时安装使用,已在archlinux 安装中实际使用
以下是KMP(Knuth-Morphis-Pratt)算法的一个基本C语言实现。KMP算法是一个改进的字符串匹配算法,它的时间复杂度是O(n + m),其中n和m分别是文本和模式的长度。该算法利用之前已经匹配过的信息来避免不必要的匹配...
KMP模板 ========================================================================
字符串匹配是计算机的基本任务之一。 举例来说,有一个字符串”BBC ABCDAB ABCDABCDABDE”,我想知道,里面是否包含另一个字符串”...许多算法可以完成这个任务,Knuth-Morris-Pratt算法(简称KMP)是最常用的之一。