这题要做的是：

  • 给定字符串 S
  • 对每个询问字符串 T
  • 统计 T 中长度为 |S| 的子串里，有多少个与 S 循环同构（即 S 的某个循环位移）

1. 为什么原代码会超时

原实现主要慢在三点：

  1. 循环中大量 substr，会反复拷贝字符串。
  2. 每个窗口重复从头计算哈希，复杂度偏高。
  3. map 查询是 O(log n)，常数和复杂度都不划算。

原代码（TLE）如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <bits/stdc++.h>

#define MAXSIZE 100006
#define ll long long

using namespace std;

map<ll,int>table;

ll hashs(string str,int len,int j)
{
    ll ans = 0;
    for (int i = j;i < len;i ++) {
        ans = ans * 131 + (ll) str[i];
    }
    return ans & 0x7fffffff;
}

int main() {
    string S;
    int q;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> S >> q;
    int len = 0;
    for(int i = 0;S[i] != '\0';i ++) {
        len ++;
    }
    S = S + S;
    for(int i = 0;i < len;i ++) {
        table[hashs(S.substr(i,len),len,i)] = 1;
    }
    while(q --) {
        int ans = 0;
        string T;
        cin >> T;
        int len2 = 0;
        for(int j = 0;T[j] != '\0';j ++) {
            len2 ++;
        }
        if(len > len2) {
            printf("0\n");
            continue;
        }
        for(int j = 0;T[j] != '\0';j ++) {
            if(table[hashs(T.substr(j,len),len,j)] == 1) {
                ans ++;
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

2. 优化后的核心思路

  1. S 的所有循环位移，等价于 SS = S + S 中前 |S| 个长度为 |S| 的窗口。
  2. 预处理这些窗口哈希，放进哈希集合。
  3. 每个 T 用固定长度窗口滚动哈希扫一遍，O(1) 判断是否命中。

3. 进一步优化点（时间 + 空间）

  • 输入：改为 fread 快读，避免 cin。
  • 输出：只用 printf。
  • 哈希：用 unsigned long long 自然溢出滚动哈希，去掉双模和大前缀数组。
  • 容器：自建开址哈希表（线性探测），比 unordered_set 更省内存、更稳常数。
  • 查询：不建 T 的前缀数组，直接滑动窗口 O(1) 更新。

复杂度：

  • 预处理：O(|S|)
  • 所有查询：O(sum |T|)
  • 额外空间：O(|S|)

4. AC 代码（C++17，printf 版）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
#include <bits/stdc++.h>
using namespace std;

using u64 = unsigned long long;

static const int MAXL = 1000005;
static const u64 BASE = 1315423911ULL;

struct FastScanner {
    static const int BUFSIZE = 1 << 20;
    int idx = 0, size = 0;
    char buf[BUFSIZE];

    inline int gc() {
        if (idx >= size) {
            size = (int)fread(buf, 1, BUFSIZE, stdin);
            idx = 0;
            if (size == 0) return 0;
        }
        return (unsigned char)buf[idx++];
    }

    inline int nextToken(char *s) {
        int c = gc();
        while (c && c <= 32) c = gc();
        if (!c) return 0;
        int p = 0;
        while (c > 32) {
            s[p++] = (char)c;
            c = gc();
        }
        s[p] = '\0';
        return p;
    }

    inline bool nextInt(int &x) {
        int c = gc();
        while (c && c <= 32) c = gc();
        if (!c) return false;
        int sign = 1;
        if (c == '-') {
            sign = -1;
            c = gc();
        }
        int v = 0;
        while (c > 32) {
            v = v * 10 + (c - '0');
            c = gc();
        }
        x = v * sign;
        return true;
    }
};

struct FastHashSet {
    vector<u64> key;
    vector<unsigned char> used;
    size_t mask = 0;

    static inline u64 splitmix64(u64 x) {
        x += 0x9e3779b97f4a7c15ULL;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9ULL;
        x = (x ^ (x >> 27)) * 0x94d049bb133111ebULL;
        return x ^ (x >> 31);
    }

    void init(size_t n) {
        size_t sz = 1;
        while (sz < (n << 1)) sz <<= 1;
        key.assign(sz, 0);
        used.assign(sz, 0);
        mask = sz - 1;
    }

    inline void insert(u64 x) {
        size_t i = (size_t)(splitmix64(x) & mask);
        while (used[i]) {
            if (key[i] == x) return;
            i = (i + 1) & mask;
        }
        used[i] = 1;
        key[i] = x;
    }

    inline bool contains(u64 x) const {
        size_t i = (size_t)(splitmix64(x) & mask);
        while (used[i]) {
            if (key[i] == x) return true;
            i = (i + 1) & mask;
        }
        return false;
    }
};

static inline u64 cv(char c) {
    return (u64)(c - 'a' + 1);
}

int main() {
    static char S[MAXL];
    static char T[MAXL];
    static char SS[MAXL * 2];

    FastScanner fs;
    int n = fs.nextToken(S);
    int q;
    fs.nextInt(q);

    memcpy(SS, S, n);
    memcpy(SS + n, S, n);
    SS[n + n] = '\0';

    u64 powN = 1;
    for (int i = 0; i < n; ++i) powN *= BASE;

    u64 h = 0;
    for (int i = 0; i < n; ++i) h = h * BASE + cv(SS[i]);

    FastHashSet rot;
    rot.init((size_t)n + 1);
    rot.insert(h);

    for (int i = n; i < 2 * n - 1; ++i) {
        h = h * BASE + cv(SS[i]) - powN * cv(SS[i - n]);
        rot.insert(h);
    }

    while (q--) {
        int m = fs.nextToken(T);
        if (m < n) {
            printf("0\n");
            continue;
        }

        u64 ht = 0;
        for (int i = 0; i < n; ++i) ht = ht * BASE + cv(T[i]);

        int ans = rot.contains(ht) ? 1 : 0;
        for (int i = n; i < m; ++i) {
            ht = ht * BASE + cv(T[i]) - powN * cv(T[i - n]);
            if (rot.contains(ht)) ++ans;
        }
        printf("%d\n", ans);
    }

    return 0;
}

5. 小结

这题是典型“固定长度窗口 + 模式集合匹配”。
把 S 的循环位移先做哈希集合，然后查询串滚动扫描，就能把复杂度压到线性级。