HDU1711 最基础的kmp算法
2024-09-30 12:20:04
Problem Description
Given two sequences of numbers : a[1], a[2], ...... , a[N], and b[1], b[2], ...... , b[M] (1 <= M <= 10000, 1 <= N <= 1000000). Your task is to find a number K which make a[K] = b[1], a[K + 1] = b[2], ...... , a[K + M - 1] = b[M]. If there are more than one K exist, output the smallest one.
Input
The first line of input is a number T which indicate the number of cases. Each case contains three lines. The first line is two numbers N and M (1 <= M <= 10000, 1 <= N <= 1000000). The second line contains N integers which indicate a[1], a[2], ...... , a[N]. The third line contains M integers which indicate b[1], b[2], ...... , b[M]. All integers are in the range of [-1000000, 1000000].
Output
For each test case, you should output one line which only contain K described above. If no such K exists, output -1 instead.
这是一道对kmp算法的最基础运用,在这里主要注意kmp函数以及得到next的函数的写法
代码如下:
#include <iostream>
#include <cstdio>
using namespace std; int n,m;
int a[],b[],next[]; void getnext (int *s,int *next){
next[]=next[]=;
for (int i=;i<m;i++){
int j=next[i];
while (j&&s[i]!=s[j])
j=next[j];
if(s[i]==s[j]) next[i+]=j+;
else next[i+]=;
}
} int kmp (int *a,int *b,int *next){
getnext (b,next);
int j=;
for (int i=;i<n;i++){
while (j&&a[i]!=b[j])
j=next[j];
if (a[i]==b[j])
j++;
if (j==m)
return i-m+;
}
return -;
} int main (){
int t;
scanf ("%d",&t);
while (t--){
scanf ("%d %d",&n,&m);
for (int i=;i<n;i++)
scanf ("%d",&a[i]);
for (int i=;i<m;i++)
scanf ("%d",&b[i]);
int ans=kmp (a,b,next);
printf ("%d\n",ans);
}
return ;
}
最新文章
- .net 面试基础题
- MySQL学习记录--生成时间日期数据
- IOS 应用生命周期
- (转)js的左右滑动触屏事件
- python3爬虫初探(五)之从爬取到保存
- LA 2797 (平面直线图PLSG) Monster Trap
- java.io.File类
- NodeJS + Socket.io搭建聊天服务器
- PHP 生命周期,Opcode 缓存。
- js数组,字符串常用方法汇总(面试必备)
- Python开发目录
- 笔记:Spring Cloud Eureka 服务发现与消费
- 设计模式之外观模式——Java语言描述
- 【原创】大数据基础之Airflow(1)简介、安装、使用
- phpstorm 报错及解决
- 《Android进阶之光》--Material Design
- C#WinForm应用程序中嵌入ECharts图表
- Centos6环境下CI(CodeIgniter)框架创建定时任务
- Node.js是用来干嘛的
- Linux之Vim学习