题解 | #.寻寻觅觅寻不到#

知识点： hash

区间 的 值为：

其中 是进制。

思路很显然，在 串中枚举连续的 个字符，放在后面，算一个 值，然后再与 串的 值比较就好了。

时间复杂度：

code

/*
work by:Ariel_
Sorce:寻寻觅觅寻不到
Knowledge:hash
Time:O(|S|)
*/
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
#include <algorithm>
#define int long long
#define rg register
using namespace std;
const int MAXN = 3e5 + 5;
const int base = 100;
const int mod = 1e9 + 7;
int read(){
    int x = 0,f = 1; char c = getchar();
    while(c < '0'||c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') {x = x*10 + c - '0'; c = getchar();}
    return x*f;
}
int T, k, fac[MAXN], _hash[MAXN], n;
char s[MAXN], t[MAXN];
int get(char s) {
  if('a' <= s && s <= 'z')return s - 'a' + 1;
  return s - 'A' + 28; 
}
int get_hash(int l, int r) {
  int ret = 0;
  for (int i = l; i <= r; i++) {
       ret = (ret * base % mod + get(s[i])) % mod;
  }
  return ret;
}
signed main(){
   T = read();
   fac[0] = 1;
   for (int i = 1; i <= MAXN; i++) fac[i] = fac[i - 1] * base % mod;
   while(T--) {
        scanf("%s%s", s + 1, t + 1);
        int n = strlen(s + 1), m = strlen(t + 1), k = read();
        if(n != m) {puts("NO"); continue;}
     int fag = 0;
     _hash[0] = 0;
     for (int i = 1; i <= n; i++)_hash[i] = (_hash[i - 1] * base % mod + get(s[i])) % mod;
     int Hash = 0;
     for (int i = 1; i <= m; i++) Hash = (Hash * base % mod + get(t[i])) % mod;
     if(k == 0) {
       if(Hash == _hash[n]) puts("YES");
       else puts("NO"); continue;
     }
     for (int l = 1, r = l + k - 1; r <= n; l++, r++) {
        int ret = (_hash[r] % mod - _hash[l - 1] * fac[r - l + 1] % mod + mod) % mod;
        int x = (_hash[l - 1] - _hash[0]  % mod + mod) % mod * fac[n - l + 1] % mod;
        int y = (_hash[n] % mod - _hash[r] * fac[n - r] % mod + mod) % mod;
        int now = (x % mod +  y * fac[r - l + 1] % mod + ret) % mod;
        if(now == Hash) {
          fag = 1;
          puts("YES");
          break;
        }
     }
     if(!fag) puts("NO");
   }
   return 0;
}