练习赛88 B 题解

注意到 不是很大，考虑枚举位置进行字符串哈希。枚举 长为 的子串 ，按照题意进行重组得到 ，与 比较。

显然直接对于每个位置哈希会超时，考虑预处理如下的哈希函数（ 是定值）：

显然，如果 ，那么可以对哈希函数进行如下处理：

所以对于 ，考虑：

显然前后两者都可预处理，中间项直接暴力求解，复杂度 。

代码用的是另一种方式，即分解 拼接 比较，思想大同小异。

#include <cstring>
#include <iostream>
#include <unordered_set>
using namespace std;

typedef long long ll;
const int max_n = 300000;
const ll mod = int(1e9) + 9;

char s[max_n+1], t[max_n+1];
ll sf[max_n+1];

ll qpow(ll bs, ll ix)
{
    ll cur = 1, mul = bs, ret = 1;
    while (cur <= ix)
    {
        if (cur & ix)
            ret = (ret * mul) % mod;
        mul = (mul * mul) % mod;
        cur <<= 1;
    }

    return ret;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int cas, k, tl;
    ll h, hh, mmul, mul, hhh, iv = qpow(131, mod - 2);

    cin >> cas;
    while (cas--)
    {
        cin >> s >> t >> k;
        if (strlen(s) != strlen(t))
        {
            cout << "NO" << endl;
            continue;
        }
        if (strcmp(s, t) == 0)
        {
            cout << "YES" << endl;
            continue;
        }

        mul = 1, h = 0;
        for (int i = 0; s[i]; i++)
        {
            h = (h + mul * s[i]) % mod;
            mul = (mul * 131) % mod;
        }

        tl = strlen(t), sf[tl] = 0;
        for (int i = tl - 1; i >= k; i--)
        {
            mul = (mul * iv) % mod;
            sf[i] = (sf[i+1] + mul * t[i-k]) % mod;
        }

        mul = 1, hh = 0;
        mmul = mul, hhh = 0;
        for (int j = tl - k; j < tl; j++)
        {
            hhh = (hhh + mmul * t[j]) % mod;
            mmul = (mmul * 131) % mod;
        }

        if ((hh + sf[k] + hhh) % mod == h)
        {
            cout << "YES" << endl;
            goto hans;
        }

        for (int i = k; i < tl; i++)
        {
            hh = (hh + mul * t[i-k]) % mod;
            mmul = mul, hhh = 0;
            for (int j = tl - k; j < tl; j++)
            {
                mmul = (mmul * 131) % mod;
                hhh = (hhh + mmul * t[j]) % mod;
            }
            if ((hh + sf[i+1] + hhh) % mod == h)
            {
                cout << "YES" << endl;
                goto hans;
            }
            mul = (mul * 131) % mod;
        }

        cout << "NO" << endl;
        hans:;
    }

    return 0;
}