Oulipo 子串查找
程序员文章站
2022-06-20 18:42:54
"题目描述" 思路 使用哈希值表示较长串的子串的值,直接比较哈希值是否相等 代码 c++ include include using namespace std; char a[1000005], b[1000005]; unsigned int sum[1000005], sumb, bt[100 ......
思路
使用哈希值表示较长串的子串的值,直接比较哈希值是否相等
代码
#include <cstdio> #include <cstring> using namespace std; char a[1000005], b[1000005]; unsigned int sum[1000005], sumb, bt[1000005]; int bs = 37, ans; int lena, lenb; unsigned int get(int st) { return sum[st + lenb - 1] - sum[st - 1] * bt[lenb]; } int main() { scanf("%s %s", a + 1, b + 1); lena = strlen(a + 1), lenb = strlen(b + 1); bt[0] = 1; for (int i = 1; i <= lena; ++i) { sum[i] = sum[i - 1] * bs + a[i]; bt[i] = bt[i - 1] * bs; } for (int i = 1; i <= lenb; ++i) { sumb = sumb * bs + b[i]; } for (int i = 1; i + lenb - 1 <= lena; ++i) { if (get(i) == sumb) ans++; } printf("%d", ans); return 0; }
上一篇: 皇太极只是努尔哈赤的庶子 为何皇位会由他来继承的呢
下一篇: 什么是乌纱帽?它是怎么来的