HDU 1711 Number Sequence

HDU 1711 Number Sequence

\(HDU\ 1711\ Number\ Sequence\)

题目链接​​​\(HDU\) \(1711\) \(Number\) \(Sequence\)​​

一、题目大意

给一段长度为\(n\)的整数\(s_1\)以及相对较小长度为\(m\)的整数\(s_2\)，问在\(s_1\)中\(s_2\)第一个成功匹配的位置在哪？不存在输出\(-1\)。

二、前置知识

​​\(Rabin\) \(Karp\)​​​​\(Kmp\)​​

三、\(Rabin\) \(Karp\)模板

/*Rabin_Karp：虽说用KMP更好，但是RK算法好理解。简单说一下RK算法的原理：首先把模式串的哈希值算出来，在文本串里不断更新模式串的长度的哈希值，若相等，则找到了，否则整个模式串的长度的哈希值向右移动一位*/#include using namespace std;typedef unsigned long long ULL;const int N = 1e4 + 10;const int M = 1e6 + 10;const ULL KEY = 100000007;int s[M], p[N];int n, m;int match() { ULL h = 1; for (int i = 0; i < n; i++) h *= KEY; //对齐0~n-1 ULL ah = 0, bh = 0; for (int i = 0; i < n; i++) ah = ah * KEY + s[i]; //模拟成KEY进制，然后利用ULL溢出的形式，相当于对2^64取模 for (int i = 0; i < n; i++) bh = bh * KEY + p[i]; //开始尝试匹配 for (int i = 0; i <= m - n; i++) { if (ah == bh) return i + 1; //如果HASH值一致，则返回匹配位置，因本题要求数组下村从1开始，所以+1后返回 if (i < m - n) ah = ah * KEY + s[i + n] - s[i] * h; //怕越界，因为数据弱，不写if也能AC，但如果模式串最后一位是0，就狒狒了，原因看EXCEL } return -1;}int main() { int T; scanf("%d", &T); while (T--) { scanf("%d%d", &m, &n); for (int i = 0; i < m; i++) scanf("%d", &s[i]); //源串 for (int i = 0; i < n; i++) scanf("%d", &p[i]); //模式串 printf("%d\n", match()); } return 0;}

四、\(Kmp\)模板

#include "bits/stdc++.h"using namespace std;const int N = 100010, M = 1000010;int n, m;int ne[N];// KMP算法的模板例题. 只不过需要换成int进行操作int s[M], p[N]; // p串短用n,s串长用m,变量名称不要记忆错误int main() { int T; scanf("%d", &T); while (T--) { scanf("%d %d", &m, &n); for (int i = 1; i <= m; i++) scanf("%d", &s[i]); //原串 for (int i = 1; i <= n; i++) scanf("%d", &p[i]); //模式串 // 求NE数组 for (int i = 2, j = 0; i <= n; i++) { while (j && p[i] != p[j + 1]) j = ne[j]; if (p[i] == p[j + 1]) j++; ne[i] = j; } // KMP bool flag = false; for (int i = 1, j = 0; i <= m; i++) { while (j && s[i] != p[j + 1]) j = ne[j]; if (s[i] == p[j + 1]) j++; if (j == n) { // 由于题目题目描述的数组下标从1开始，所以追加1 printf("%d\n", i - n + 1); flag = true; //防止多次匹配成功：本题要求输出第一个匹配，所以需要及时break,并且注释掉 j=ne[j] break; // j = ne[j]; } } //如果没有匹配成功，则输出-1 if (!flag) printf("%d\n", -1); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。