HDU-1711-Number Sequence-白红宇

HDU-1711-Number Sequence

阅读量：7201 次

发布时间：2019-06-29

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

链接：https://vjudge.net/problem/HDU-1711

题意：

给出两个数字序列 : a[1], a[2], ...... , a[N], 和 b[1], b[2], ...... , b[M] (1 <= M <= 10000, 1 <= N <= 1000000). 你的任务是找到一个数字K满足： a[K] = b[1], a[K + 1] = b[2], ...... , a[K + M - 1] = b[M]. 如果有多个K满足题意，请你输出最小的那个K。

思路：

KMP找子串第一次出现位置。

代码：

#include 
     
      #include 
      
       #include 
       
        #include 
        #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              using namespace std;typedef long long LL;const int MAXN = 1e6 + 10;const int MAXM = 1e4 + 10;int Next[MAXM];int a[MAXN], b[MAXM];void Get_Next(int m){ int k = -1; int j = 0; Next[j] = k; while (j < m) { if (k == -1 || b[j] == b[k]) { j++; k++; Next[j] = k; } else k = Next[k]; }}int Kmp(int n, int m){ int i = 0; int j = 0; Get_Next(m); while (i < n && j < m) { if (j == -1 || a[i] == b[j]) i++, j++; else j = Next[j]; } if (j == m) return i - j + 1; else return -1;}int main(){ int t, n, m; scanf("%d", &t); while (t--) { memset(Next, 0, sizeof(Next)); 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]); cout << Kmp(n, m) << endl; } return 0;}

转载于:https://www.cnblogs.com/YDDDD/p/10552490.html

你可能感兴趣的文章