[kuangbin带你飞]专题十六 KMP & 扩展KMP & Manacher A - Number Sequence HDU

[kuangbin带你飞]专题十六 KMP & 扩展KMP & Manacher A - Number Sequence HDU - 1711 (kmp)

阅读量：4557 次

发布时间：2019-06-08

本文共 1537 字，大约阅读时间需要 5 分钟。

[kuangbin带你飞]专题十六 KMP & 扩展KMP & Manacher

A - Number Sequence

HDU - 1711

题目链接：

题目：

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.

InputThe 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].

OutputFor each test case, you should output one line which only contain K described above. If no such K exists, output -1 instead.

Sample Input

213 51 2 1 2 3 1 2 3 1 3 2 1 21 2 3 1 313 51 2 1 2 3 1 2 3 1 3 2 1 21 2 3 2 1

Sample Output

6-1 题意：给你两个序列a,b，找出b序列在a中出现的位置，利用kmp算法

//// Created by hanyu on 2019/8/13.//#include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include
             
              #include
              using namespace std;typedef long long ll;const int maxn=1e6+7;#define MAX 0x3f3f3f3fint a[maxn],b[maxn];int nextt[maxn];int n,m;void getnext(){ int i=0,j=-1; nextt[0]=-1; while(i

转载于:https://www.cnblogs.com/Vampire6/p/11348481.html

你可能感兴趣的文章