题解 | #白兔的字符串#

注意到T的循环同构的字串有|T|个,因此把这部分存起来,对于每一个$S_{i}S\_i$,枚举所有的字串,判断即可.

如何计算与T循环同构的字符串的hash值:

不妨假设原串为: $t_0{t}_1{t}_2{t}_3,\mathrm{哈}\mathrm{希}\mathrm{值}\mathrm{为}hasht\_0t\_1t\_2t\_3,\; 哈希值为hash$

把$t_0\mathrm{删}\mathrm{除}:hash-=t_0\ast P^{n-1}t\_0删除:\; hash\; -=\; t\_0\; *\; P\; ^\; \{n-1\}$

整体左移1位: $hash\ast =Phash\; *=\; P$

$t_{0}t\_0$移动到末尾: $hash+=T_{0}hash\; +=\; T\_0$

AC 代码

using ULL = unsigned long long;
void solve() {
    std::string t;
    std::cin >> t;

    int len = t.size();
    std::vector<ULL> p(1000010);
    constexpr int P = 131;
    p[0] = 1;
    for (int i = 1; i <= 1000000; i ++) {
        p[i] = p[i - 1] * P;
    }
    int hash = 0;
    for (int i = 0; i < len; i ++) {
        hash = hash * P + t[i];
    }
    
    std::unordered_set<int> st;
    for (int i = 0; i < len; i ++) {
        hash = (hash - t[i] * p[len - 1]) * P + t[i];
        st.insert(hash);
    }

    int n;
    std::cin >> n;
    for (int i = 0; i < n; i ++) {
        std::string s;
        std::cin >> s;
        int m = s.size();
        if (m < len) {
            std::cout << 0 << "\n";
        } else {
            std::vector<int> h(m + 1);
            for (int i = 0; i < m; i ++) {
                h[i + 1] = h[i] * P + s[i];
            }
            int ans = 0;
            for (int l = 1; l + len - 1 <= m; l ++) {
                int r = l + len - 1;
                int now = h[r] - h[l - 1] * p[r - l + 1];
                if (st.count(now)) ans ++;
            }
            std::cout << ans << "\n";
        }
    }
}