HDU 1711 Number Sequence
【摘要】 题目链接~~>
做题感悟:今天学习了一下KMP虽然还处于迷茫状态,但是照着模版很容易就把这题A了。
解题思路:KMP 裸题(可以用作模版)。
代码:
#include<stdio.h>#include<iostream>#include<map>#include<stack>#include<string&g...
做题感悟:今天学习了一下KMP虽然还处于迷茫状态,但是照着模版很容易就把这题A了。
解题思路:KMP 裸题(可以用作模版)。
代码:
-
#include<stdio.h>
-
#include<iostream>
-
#include<map>
-
#include<stack>
-
#include<string>
-
#include<string.h>
-
#include<stdlib.h>
-
#include<math.h>
-
#include<vector>
-
#include<queue>
-
#include<algorithm>
-
using namespace std ;
-
#define LEN sizeof(struct node)
-
const double PI = 3.1415926 ;
-
const double INF = 99999999 ;
-
const int MX =1000005 ;
-
int n ,m ;
-
int a[MX],b[MX],next[MX] ;
-
void getnext() // 求next[] 数组
-
{
-
int i=0,j=-1 ;
-
next[0]=-1 ;
-
while(i<m-1)
-
{
-
if(j==-1||b[i]==b[j])// 重新匹配 || 两者相等比较下一个
-
{
-
i++ ;
-
j++ ;
-
next[i]=j ;
-
}
-
else // b[i] != b[j] 则到有最多匹配的下标的下一个值去再匹配
-
j=next[j] ;
-
}
-
}
-
int KMP()
-
{
-
int i=0,j=0 ;
-
getnext() ;
-
while(i<n)
-
{
-
if(j==-1||a[i]==b[j]) // 从头开始匹配||匹配成功继续比较下一对
-
{
-
i++ ;
-
j++ ;
-
}
-
else
-
j=next[j] ;
-
if(j==m) // 如果匹配成功返回起始匹配点
-
return i-m+1 ;
-
}
-
return -1 ;
-
}
-
int main()
-
{
-
int T ;
-
scanf("%d",&T) ;
-
while(T--)
-
{
-
scanf("%d%d",&n,&m) ;
-
for(int i=0 ;i<n ;i++)
-
scanf("%d",&a[i]) ;
-
for(int i=0 ;i<m ;i++)
-
scanf("%d",&b[i]) ;
-
printf("%d\n",KMP()) ;
-
}
-
return 0 ;
-
}
文章来源: blog.csdn.net,作者:Linux猿,版权归原作者所有,如需转载,请联系作者。
原文链接:blog.csdn.net/nyist_zxp/article/details/21741451
【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱:
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论(0)