杭电多校补题

youhualiuh / 2024-07-20 / 原文

1001.循环位移

题意：

定义一个字符串[A] 它代表着是一个循环位移的字符串. 给你T组数据，字符串A, B.问你在B字符串中有多少子串是[A]

分析样例:

如何解决这个问题,我的方法是字符串哈希

为了处理 A 的循环位移，代码将 A 自身与自身拼接，形成 A+A。这样，所有可能的循环位移都可以作为 A+A 的子串出现
就将所有A的循环位移字符串的哈希值储存进map里 再去枚举B的长度为A的哈希值,去B的长度为A统计是否映射进A里,累加答案就是最终答案

Code:

#include<bits/stdc++.h>
    
using namespace std;
typedef unsigned long long ull; 
const int N = 1048580 * 2; 
const int P = 131;
ull p[N], h1[N], h2[N];

void solve() {
    string a, b;
    cin >> a >> b;
    int n = a.size(), m = b.size();
    a = a + a;
    for (int i = 0; i < (n << 1); i++) {
        h1[i + 1] = h1[i] * P + a[i]; 
    }
    for (int i = 0; i < m; i++) {
        h2[i + 1] = h2[i] * P + b[i]; 
    }
    map <ull, int> mp;
    for (int i = 0; i < n; i++) {
        mp[h1[i + n] - h1[i] * p[n]]++;
    }
    int ans = 0;
    for (int i = 0; i <= m - n; i++) {
        ans += mp[h2[i + n] - h2[i] * p[n]];
    }
    cout << ans << '\n';
}
    
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    p[0] = 1;
    for (int i = 1; i < N; i++) {
        p[i] = p[i - 1] * P;
    }
    int _; cin >> _;
    while(_--) solve();
    return 0;
}