Number Sequence HDU - 1711 （Hash或KMP）-白红宇

Number Sequence HDU - 1711 （Hash或KMP）

阅读量：6332 次

发布时间：2019-06-22

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

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.

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

很简单的题目，是一道KMP的模板题，但也是Hash的模板题。

Hash代码：

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              #include 
               
                #define endl '\n'#define sc(x) scanf("%d",&x)using namespace std;typedef unsigned long long ULL;const int size=1e6+5;ULL H[size],P[size];int s[size];void Hash(int len,int PA=2333){ H[0]=0; P[0]=1; for(int i=1;i<=len;i++) { H[i]=H[i-1]*PA+s[i]+2000000; P[i]=P[i-1]*PA; }}ULL code(int l,int r){ return H[r]-H[l-1]*P[r-l+1];}unordered_map
                
                  mp;int main(){ int t; sc(t); while(t--) { int n,m; sc(n),sc(m); for(int i=1;i<=n;i++) sc(s[i]); Hash(n); ULL s2=0; int t; for(int i=0;i

KMP代码：

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              #define endl '\n'#define sc(x) scanf("%d",&x)using namespace std;int nxt[10005];int ss[1000005],s[10005]; int n,m;void getnext(){ nxt[0]=0,nxt[1]=0; int j=0; for(int i=1;i

转载于:https://www.cnblogs.com/fly-white/p/10092744.html

你可能感兴趣的文章

linux复制指定目录下的全部文件到另一个目录中，linux cp 文件夹