#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<int, int> pii;
typedef pair<ll, ll> PII;
#define pb emplace_back
//#define int ll
#define all(a) a.begin(),a.end()
#define x first
#define y second
#define ps push_back
#define endl '\n'
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
void solve();
const int N = 1e6 + 10;
ull p1[N],p2[N],h1[N],h2[N];
ll n;
string s1,s2;
ll ls1,ls2;
const ll P = 131;
ull has1;
signed main() {
IOS;
ll t;
cin >> t;
while(t--)
solve();
return 0;
}
ull get1(int l,int r)
{
if(l < 1 || l > r || r > ls1)
return 0;
return h1[r] - h1[l-1] * p1[r - l + 1];
}
ull get2(int l,int r)
{
if(l < 1 || l > r || r > ls2)
return 0;
return h2[r] - h2[l-1] * p2[r - l + 1];
}
void solve() {
s1.clear(),s2.clear();
cin >> s1 >> s2;
ll len = s1.size();
s1 = s1 + s1;
ls1 = s1.size(),ls2 = s2.size();
s1 = ' ' + s1;
s2 = ' ' + s2;
p1[0] = p2[0] = 1;
// s1 的 hash值
for(int i = 1; i <= ls1; ++ i)
{
h1[i] = h1[i-1]*P + s1[i] - 'A';
p1[i] = p1[i-1]*P;// 进制
}
// s2 的 hash值
for(int i = 1; i <= ls2; ++ i)
{
h2[i] = h2[i - 1] * P + s2[i] - 'A';
p2[i] = p2[i - 1] * P;
}
map<ll,ll> mp;
for(int i = 1; i <= ls2; ++ i)
{
ll j = i + len - 1;
if(j > ls2) break;
mp[get2(i,j)] ++;
}
ll ans = 0;
for(int i = 1; i <= len; ++ i)
{
ll j = i + len - 1;
if(j > ls1) break;
ans += mp[get1(i,j)];
}
cout << ans << endl;
}
#pragma GCC optimize("Ofast,inline,unroll-loops,fast-math,no-stack-protector")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
const int N = 1e6;
const int mod = 131;
int lt, ls;
ull p1[N], h1[N], p2[N], h2[N];
// 计算字符串t从l到r的哈希值
ull get1(int l, int r)
{
if (l > r || l < 1 || r > lt)
return 0;
return h1[r] - h1[l - 1] * p1[r - l + 1];
}
// 计算字符串s从l到r的哈希值
ull get2(int l, int r)
{
if (l > r || l < 1 || r > ls)
return 0;
return h2[r] - h2[l - 1] * p2[r - l + 1];
}
void solve()
{
string t, s;
cin >> t >> s;
int len = t.size();
t = t + t; // 将t复制一份拼接在原字符串后面,方便后续计算循环位移
lt = t.size(), ls = s.size();
t = " " + t; // 在字符串开头添加一个空格,方便计算哈希值
s = " " + s;
p1[0] = p2[0] = 1;
for (int i = 1; i <= lt; i++)
{
h1[i] = h1[i - 1] * mod + t[i] - '0'; // 计算t的哈希值
p1[i] = p1[i - 1] * mod; // 计算模数的幂次方
}
for (int i = 1; i <= ls; i++)
{
h2[i] = h2[i - 1] * mod + s[i] - '0'; // 计算s的哈希值
p2[i] = p2[i - 1] * mod; // 计算模数的幂次方
}
map<ll, ll> mp;
for (int i = 1; i <= ls; i++)
{
int j = i + len - 1;
if (j > ls)
break;
mp[get2(i, j)]++; // 统计s中所有长度为len的子串的哈希值出现次数
}
ll ans = 0;
for (int i = 1; i <= len; i++)
{
int j = i + len - 1;
if (j > lt)
break;
ans += mp[get1(i, j)]; // 累加s中子串在t的循环位移版本中出现的次数
}
cout << ans << endl; // 输出结果
}
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int _ = 1;
cin >> _;
while (_--)
solve();
return 0;
}
标签:return,ull,int,s1,long,哈希,字符串,ll From: https://blog.csdn.net/2303_79552392/article/details/140552447