2022香农先修班第十二次课题解

模板题。解析请查看先修班第十二次课课件。

字符串哈希解法：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define mn 2000010
char s[mn], t[mn];
ull p = 131, pw[mn], h[mn], ht, n, m, cnt;
signed main()
{
    pw[0] = 1;
    for (ll i = 1; i < mn; ++i)
    {
        pw[i] = pw[i - 1] * p;
    }
    scanf("%s%s", s, t);
    n = strlen(s), m = strlen(t);
    for (ull i = 0; i < n; ++i)
    {
        h[i + 1] = h[i] * p + s[i];
    }
    for (ull i = 0; i < m; ++i)
    {
        ht = ht * p + t[i];
    }
    for (ull lf = 1, rf = m; rf <= n; ++lf, ++rf)
    {
        if (h[rf] - h[lf - 1] * pw[rf - lf + 1] == ht)
        {
            printf("%lld ", lf), ++cnt;
        }
    }
    if (!cnt)
    {
        printf("-1");
    }
    return 0;
}

如果您需要测试数据，请使用如下程序生成测试数据：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define repe(i, a, b) for (ll i = a; i <= b; ++i)
ll cnt;
void alters()
{
    ++cnt;
    freopen(("strhash" + to_string(cnt) + ".in").c_str(), "w", stdout);
}
signed main()
{
    alters(); // 1
    repe(i, 1, 2e6) putchar('_');
    putchar('\n');
    repe(i, 1, 2e6) putchar('_');

    alters(); // 2
    repe(i, 1, 2e6) putchar('z');
    putchar('\n');
    repe(i, 1, 1e6) putchar('z');

    alters(); // 3
    repe(i, 1, 2e6) putchar('A');
    putchar('\n');
    repe(i, 1, 1e6 - 1) putchar('A');
    putchar('a');

    alters(); // 4
    repe(i, 1, 2e6) putchar('_');
    putchar('\n');
    repe(i, 1, 2e6 - 1) putchar('_');
    putchar('-');

    alters(); // 5
    repe(i, 1, 2e6) putchar('0');
    putchar('\n'), putchar('0');

    alters(); // 6
    repe(i, 1, 2e6) putchar('a' + (rand() % 26));
    putchar('\n'), putchar('a' + (rand() % 26));

    alters(); // 7
    repe(i, 1, 2e6) putchar('a' + (rand() % 26));
    putchar('\n');
    repe(i, 1, 3) putchar('a' + (rand() % 26));

    alters(); // 8
    repe(i, 1, 2e6) putchar('a' + (rand() % 26));
    putchar('\n');
    repe(i, 1, 2e6) putchar('a' + (rand() % 26));
    return 0;
}