题解 | #白兔的字符串#

注意到T的循环同构的字串有 个,因此把这部分存起来,对于每一个 , 枚举所有的字串,判断即可.

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

不妨假设原串为:

把 删除:

整体左移1位:

移动到末尾:

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";
        }
    }
}