[SDOI2015] 双旋转字符串

题意

给定两个字符串集合 S 和 T。

S 中每个字符串长度都是 N
T 中每个字符串长度都是 M
N + M 一定是偶数

要求统计有多少对 (S_i, T_j)，使得拼接串 S_i + T_j 的前一半和后一半长度相同，并且后一半可以由前一半旋转得到。

思路

先看一个可以直接验证想法的朴素解：

cpp

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#include <bits/stdc++.h>
using namespace std;

int total_s, total_t, n, m;
vector<string> s_list, t_list;

bool is_rotation(const string &a, const string &b) {
    if (a.size() != b.size()) {
        return false;
    }
    string t = a + a;
    return t.find(b) != string::npos;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> total_s >> total_t >> n >> m;
    s_list.resize(total_s);
    t_list.resize(total_t);
    for (int i = 0; i < total_s; i++) {
        cin >> s_list[i];
    }
    for (int i = 0; i < total_t; i++) {
        cin >> t_list[i];
    }

    int half = (n + m) / 2;
    long long answer = 0;

    // brute.cpp：直接枚举每一对 (S_i, T_j)，检查拼接后前半段与后半段是否为旋转关系。
    for (int i = 0; i < total_s; i++) {
        for (int j = 0; j < total_t; j++) {
            string w = s_list[i] + t_list[j];
            string u = w.substr(0, half);
            string v = w.substr(half, half);
            if (is_rotation(u, v)) {
                answer++;
            }
        }
    }

    cout << answer << '\n';

    return 0;
}

暴力做法就是枚举每一对 (S_i,T_j)，拼起来后把前半段和后半段取出，再判断它们是否互为旋转。这个方法复杂度太高，只适合很小的数据。

设 half = (N + M) / 2。

核心在于按 N 和 M 的大小关系分情况建模。

情况一：`N >= M`

此时把 S_i 记成：

P：前 half 个字符
Q：后 N-half 个字符

拼接后前半段就是 P。
后半段则是 Q + T_j。

要满足双旋转性，就要求：

Q + T_j 是 P 的某个旋转。

这等价于：

在循环串 P + P 中找一个起点
从这个起点开始长度 N-half 的那一段必须等于 Q
紧随其后的长度 M 的那一段就是候选 T_j

所以对每个 S_i，我们只需要：

在 P+P 中找 Q 的所有出现位置
每个出现位置导出一个候选 T
看这个候选 T 是否在集合 T 中出现

为了高效找 Q 的出现位置，使用 KMP；为了高效查候选串是否在 T 集合中，使用哈希。

情况二：`N < M`

完全对称地处理 T_j。

把 T_j 记成：

X：前 half-N 个字符
Y：后 half 个字符

此时后一半就是 Y，前一半是 S_i + X。
要求前一半是 Y 的某个旋转。

于是转成：

在 Y+Y 中找 X 的出现位置
由这些位置反推出候选 S
在集合 S 中查有没有这个候选

两种情况都只需要做：

KMP 找匹配位置
哈希取候选子串
对同一个原串产生的重复候选去重
用哈希表统计另一侧集合中的出现次数

这样就可以在线性级别处理所有字符串内容。

代码

cpp

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
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232#include <bits/stdc++.h>
using namespace std;

typedef unsigned long long ull;

const ull BASE1 = 131;
const ull BASE2 = 13331;

struct HashKey {
    ull h1, h2;

    bool operator==(const HashKey &other) const {
        return h1 == other.h1 && h2 == other.h2;
    }

    bool operator<(const HashKey &other) const {
        if (h1 != other.h1) {
            return h1 < other.h1;
        }
        return h2 < other.h2;
    }
};

struct KeyHasher {
    size_t operator()(const HashKey &key) const {
        ull x = key.h1 * 1000003ULL;
        ull y = key.h2 * 1000033ULL;
        return (size_t)(x ^ (y << 1) ^ (y >> 3));
    }
};

int total_s, total_t, n, m;
vector<string> s_list, t_list;
vector<ull> pow1_base, pow2_base;

int char_value(char ch) {
    return (unsigned char)ch + 1;
}

void build_pow(int max_len) {
    pow1_base.assign(max_len + 1, 0);
    pow2_base.assign(max_len + 1, 0);
    pow1_base[0] = 1;
    pow2_base[0] = 1;
    for (int i = 1; i <= max_len; i++) {
        pow1_base[i] = pow1_base[i - 1] * BASE1;
        pow2_base[i] = pow2_base[i - 1] * BASE2;
    }
}

void build_prefix_hash(const string &s, vector<ull> &h1, vector<ull> &h2) {
    int len = (int)s.size();
    h1.assign(len + 1, 0);
    h2.assign(len + 1, 0);
    for (int i = 0; i < len; i++) {
        h1[i + 1] = h1[i] * BASE1 + char_value(s[i]);
        h2[i + 1] = h2[i] * BASE2 + char_value(s[i]);
    }
}

HashKey get_sub_hash(const vector<ull> &h1, const vector<ull> &h2, int l, int len) {
    HashKey res;
    res.h1 = h1[l + len] - h1[l] * pow1_base[len];
    res.h2 = h2[l + len] - h2[l] * pow2_base[len];
    return res;
}

HashKey hash_whole_string(const string &s) {
    ull h1 = 0, h2 = 0;
    for (int i = 0; i < (int)s.size(); i++) {
        h1 = h1 * BASE1 + char_value(s[i]);
        h2 = h2 * BASE2 + char_value(s[i]);
    }
    return {h1, h2};
}

vector<int> prefix_function(const string &pat) {
    int len = (int)pat.size();
    vector<int> pi(len, 0);
    for (int i = 1; i < len; i++) {
        int j = pi[i - 1];
        while (j > 0 && pat[i] != pat[j]) {
            j = pi[j - 1];
        }
        if (pat[i] == pat[j]) {
            j++;
        }
        pi[i] = j;
    }
    return pi;
}

// 在 text 中寻找 pattern 的所有出现位置。
vector<int> kmp_match(const string &text, const string &pattern) {
    vector<int> result;
    if (pattern.empty()) {
        return result;
    }
    vector<int> pi = prefix_function(pattern);
    int j = 0;
    for (int i = 0; i < (int)text.size(); i++) {
        while (j > 0 && text[i] != pattern[j]) {
            j = pi[j - 1];
        }
        if (text[i] == pattern[j]) {
            j++;
        }
        if (j == (int)pattern.size()) {
            result.push_back(i - j + 1);
            j = pi[j - 1];
        }
    }
    return result;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> total_s >> total_t >> n >> m;
    s_list.resize(total_s);
    t_list.resize(total_t);
    for (int i = 0; i < total_s; i++) {
        cin >> s_list[i];
    }
    for (int i = 0; i < total_t; i++) {
        cin >> t_list[i];
    }

    int half = (n + m) / 2;
    int max_len = max(max(n, m), half * 2);
    build_pow(max_len);

    long long answer = 0;

    if (n >= m) {
        int d = n - half;

        unordered_map<HashKey, int, KeyHasher> t_count;
        t_count.reserve(total_t * 2 + 1);
        for (int i = 0; i < total_t; i++) {
            t_count[hash_whole_string(t_list[i])]++;
        }

        for (int i = 0; i < total_s; i++) {
            const string &a = s_list[i];
            string p = a.substr(0, half);
            string q = a.substr(half, d);
            string text = p + p;

            vector<ull> h1, h2;
            build_prefix_hash(text, h1, h2);

            vector<HashKey> cand;
            if (d == 0) {
                cand.reserve(half);
                for (int st = 0; st < half; st++) {
                    cand.push_back(get_sub_hash(h1, h2, st, m));
                }
            }
            else {
                vector<int> pos = kmp_match(text, q);
                cand.reserve(pos.size());
                for (int idx = 0; idx < (int)pos.size(); idx++) {
                    int st = pos[idx];
                    if (st < half) {
                        cand.push_back(get_sub_hash(h1, h2, st + d, m));
                    }
                }
            }

            sort(cand.begin(), cand.end());
            cand.erase(unique(cand.begin(), cand.end()), cand.end());
            for (int j = 0; j < (int)cand.size(); j++) {
                unordered_map<HashKey, int, KeyHasher>::iterator it = t_count.find(cand[j]);
                if (it != t_count.end()) {
                    answer += it->second;
                }
            }
        }
    }
    else {
        int e = half - n;

        unordered_map<HashKey, int, KeyHasher> s_count;
        s_count.reserve(total_s * 2 + 1);
        for (int i = 0; i < total_s; i++) {
            s_count[hash_whole_string(s_list[i])]++;
        }

        for (int i = 0; i < total_t; i++) {
            const string &b = t_list[i];
            string x = b.substr(0, e);
            string y = b.substr(e, half);
            string text = y + y;

            vector<ull> h1, h2;
            build_prefix_hash(text, h1, h2);

            vector<HashKey> cand;
            if (e == 0) {
                cand.reserve(half);
                for (int st = 0; st < half; st++) {
                    cand.push_back(get_sub_hash(h1, h2, st, n));
                }
            }
            else {
                vector<int> pos = kmp_match(text, x);
                cand.reserve(pos.size());
                for (int idx = 0; idx < (int)pos.size(); idx++) {
                    int st = pos[idx];
                    if (st >= n && st < n + half) {
                        cand.push_back(get_sub_hash(h1, h2, st - n, n));
                    }
                }
            }

            sort(cand.begin(), cand.end());
            cand.erase(unique(cand.begin(), cand.end()), cand.end());
            for (int j = 0; j < (int)cand.size(); j++) {
                unordered_map<HashKey, int, KeyHasher>::iterator it = s_count.find(cand[j]);
                if (it != s_count.end()) {
                    answer += it->second;
                }
            }
        }
    }

    cout << answer << '\n';

    return 0;
}

复杂度

设所有字符串总长度为 Lsum。

每个字符串只会被做常数次：

构造循环串
跑一次 KMP
对若干匹配位置取哈希并查表

因此总时间复杂度可以看作 $O(Lsum + 匹配位置总数)$ ，实际实现中再加上一点去重排序的代价。
空间复杂度是 $O(Lsum)$ 。

总结

这题最重要的是把“前半和后半互为旋转”拆开，并根据 N、M 的大小关系，把问题压缩成：

在一个循环串里找固定前后缀关系
由匹配位置反推出另一侧字符串

本质上是字符串建模 + KMP + 哈希的组合题。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。