当前位置:网站首页>hdoj 1711 KMP Number Sequence
hdoj 1711 KMP Number Sequence
2021-01-22 14:15:44 【xindoo】
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.
Sample Input
2 13 5 1 2 1 2 3 1 2 3 1 3 2 1 2 1 2 3 1 3 13 5 1 2 1 2 3 1 2 3 1 3 2 1 2 1 2 3 2 1
Sample Output
6 -1 #include <stdio.h> int n, m; int a[1000005]; int b[10005]; int f[10005]; void getfail() { f[0] = 0; f[1] = 0; for (int i = 1; i < m; i++) { int j = f[i]; while (j && b[i] != b[j]) j = f[j]; f[i+1] = b[j] == b[i] ? j + 1 : 0; } } int main() { int flag, i, j, t; scanf("%d",&t); while (t--) { scanf("%d %d",&n,&m); for (i = 0; i < n; i++) scanf("%d",&a[i]); for (i = 0; i < m; i++) scanf("%d",&b[i]); getfail(); for (i = 0;i <= m; i++) printf("%d ",f[i]); puts(""); flag = 1; j = 0; for (i = 0;i < n;i++) { while (j && b[j] != a[i]) j = f[j]; if (b[j] == a[i]) j++; if (j == m) { flag = 0; printf("%d\n",i - m + 1); } } if (flag) puts("-1"); } return 0; }
本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。
版权声明
本文为[xindoo]所创,转载请带上原文链接,感谢
https://cloud.tencent.com/developer/article/1778391
边栏推荐
猜你喜欢
随机推荐
- Thinking construction and skill realization of recursion
- CodeForces 808G Anthem of Berland 前缀函数 KMP DP
- Linear DP initial-2-monotone queue optimization
- Linear DP initial-2-monotone queue optimization
- Dynamic programming the longest common ascending subsequence-n ^ 2 solution
- 【蓝桥杯】走方格
- Blue Bridge Cup
- HDU 0-1 Backpack
- P2453 [SDOI2006]最短距离
- P2051 [AHOI2009]中国象棋
- P2622 light off problem II
- P2051 [ahoi2009] Chinese chess
- 动态规划_备忘录法_矩阵链乘问题
- 动态规划_每对结点间的最短路径_Floyd
- [期望DP][纪中]【2010集训队出题】彩色圆环
- 二维数组 A[m][n] 按行优先和按列优先的 下标地址转换公式
- asd
- 状压DP详解(2)--状态的预处理+经典例题剖析--POJ1185炮兵阵地
- Subscript address translation formula of two dimensional array a [M] [n] with row priority and column priority
- 实现函数输出n行数字金字塔
- 立方阶时间复杂度 O(n^3) 详解
- asd
- The best match of p1559 athletes
- Hangzhou Electric OJ 11 page 2026 / / calculate the average score of each student and the average score of each course, and output the number of students whose scores in each subject are greater than or equal to the average score.
- hdu 1848(SG函数)
- hdu 1024(滚动数组+动态规划)
- 【POJ 2250】Compromise(最长公共子序列LCS)
- Detailed explanation of cubic time complexity O (n ^ 3)
- Exercise: find the greatest common divisor of two numbers by recursion
- BZOJ1013:[JSOI2008]球形空间产生器sphere(高斯消元)
- HDU 1024 (rolling array + dynamic programming)
- Luogu 1164 a la carte
- Leetcode 62. Different paths