题解 | 寻寻觅觅寻不到

【B.寻寻觅觅寻不到】 题解

看有位大佬写的题解挺长的，感觉这题目考察点就一个：区间字符串哈希
对于区间的字符串哈希值，公式如下：

题目也就是从字串中取出长度为 的子串，将其放在主串的后面构成新的串，看是否和文本串匹配，这里指 串。

所以就是拼接的问题了，由于我们取了长度为 的子串，那么整个主串就分成三分，分别是 ，对应的我们分别用 表示。那么组合成的新的主串的哈希值我们可以比着区间的去做：

其中 表示进制， 表示区间长度。实现的思路主要就是往前进位嘛。
看数据范围非常友好，就直接暴力枚举区间，判断时否和 的哈希值相同就好了。

清奇的码风

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <map>
#include <cstring>
#define int long long 
using namespace std;
const int B=4*1e5+10;
const int base=131;
const int mod=1e9+7;
int T;
int ha[B];
int haa[B];
int jc[B];
char a[B],c[B];
int read() {int x;scanf("%lld",&x);return x;}
int get(int l,int r)
{
    return (ha[r]%mod-ha[l-1]%mod*jc[r-l+1]%mod+mod)%mod;
}
void solve()
{
    cin>>a+1;
    cin>>c+1; 
    int k=read();
    int la=strlen(a+1); ha[0]=0;
    int lc=strlen(c+1);
    int sum=0;
    for (int i=1;i<=la;i++) ha[i]=(ha[i-1]*base%mod+a[i]%mod+mod)%mod;
    for (int i=1;i<=lc;i++) sum=(sum%mod*base%mod+c[i]%mod+mod)%mod; 
    for (int l=1;l+k-1<=la;l++)
    {
        int s1=get(1,l-1);
        int s2=get(l,l+k-1);
        int s3=get(l+k,la);
        int ans=(s1%mod*jc[la-l+1]%mod+s3%mod*jc[k]%mod+s2)%mod;
        if (ans==sum) {printf("YES\n");return;}
    }
    printf("NO\n");return;
}
signed main()
{
    jc[0]=1;
    for (int i=1;i<=B-2;i++) jc[i]=(jc[i-1]%mod*base%mod)%mod;
    T=read();
    while (T--) solve();
}