c/c++语言开发共享Oulipo 子串查找

思路

使用哈希值表示较长串的子串的值，直接比较哈希值是否相等

代码

#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; }