原题呈现

题目描述#

书上记载，这两串密语可能拥有共同的“基础咒语”．如果一个短咒语 $t$ 可以通过将自身连续拼接多次来完全构成字符串 $s_1$ ，同时也可以通过连续拼接多次完全构成字符串 $s_2$ （即 $t$ 同时是 $s_1$ 和 $s_2$ 的循环节，或称为公共除数），那么 $t$ 就是一个合法的“基础咒语”．

小信想要彻底解开魔法书的秘密，他需要计算出，到底有多少个不同的字符串 $t$ 能够同时满足上述条件？

输入格式#

第一行包含一个字符串 $s_1$ ．

第二行包含一个字符串 $s_2$ ．

保证两个字符串均只包含小写英文字母，且中间没有空格．

输出格式#

输出一行一个整数，表示满足条件的字符串 $t$ 的数量．如果不存在这样的字符串 $t$ ，则输出 0．

样例#

输入 #1#

1
abcdabcd
2
abcdabcdabcdabcd

输出 #1#

1
2

样例解释#

对于样例 # 1，满足条件的“基础咒语” $t$ 有两个：

abcd：拼接 2 次可得 $s_1$ ，拼接 4 次可得 $s_2$ ．
abcdabcd：拼接 1 次可得 $s_1$ ，拼接 2 次可得 $s_2$ ．

数据范围#

Subtask	分值	数据范围	特殊性质
1	30	$1\le s_1, s_2 \le 10^3$	无
2	30	$1\le s_1, s_2 \le 10^5$	保证两个字符串都由同一个较短字符串重复得到
3	40	$1\le s_1, s_2 \le 10^7$	无

由题意可得，这两个字符串 $s_1$ 、 $s_2$ 的循环节的长度，一定是原来两个字符串长度最大公因数的因数．

因此，尝试枚举循环节的长度：

1
int maxLen = gcd(sx.size(), sy.size());
2
vector<int> fac;
3
for (int i = 1; i <= sqrt(maxLen); i++) {
4
  if (maxLen % i == 0) {
5
    fac.push_back(i);
6
    if (i * i != maxLen) {
7
      fac.push_back(maxLen / i);
8
    }
9
  }
10
}

对于每一个长度 $d$ ，只需要验证：

$s_1[0..d-1]$ 是 $s_1$ （设长度为 $n$ ）的循环节，即 $s_1$ 去掉前面一节循环节和去掉后面一节循环节是相同的： $s_1[0, n - d - 1] = s_1[d, n - 1]$
$s_2[0..d-1]$ 是 $s_2$ 的循环节，同上．
$s_1[0..d-1]=s_2[0..d-1]$

所有的字符串判等可以使用哈希优化。

标程

以下标程使用双哈希来快速进行字符串判等。

1
#include <bits/stdc++.h>
2
using namespace std;
3
#define int long long
4
const int BASE = 128;
5
const int MOD1 = 1e9 + 7;
6
const int MOD2 = 1e9 + 9;
7
const int N = 1e7 + 10;
8
int la1[N], la2[N], lb1[N], lb2[N], p1[N], p2[N];
9
string sx, sy;
10

11
struct Hash {
12
    int *h;
13
    int *p;
14
    int MOD;
15
    Hash(int *h, int *p, int MOD) {
16
        this->h = h;
17
        this->p = p;
18
        this->MOD = MOD;
19
    }
20
    void init(string &str) {
21
        p[0] = 1;
22
        for (int i = 1; i <= str.size(); i++) {
23
            (h[i] = 1ll * h[i - 1] * BASE % MOD + str[i - 1]) %= MOD;
24
            p[i] = p[i - 1] * BASE % MOD;
25
        }
26
    }
27
    /**
28
     * 获取子串 hash，0-based
29
     */
30
    int get(int l, int r) {
31
        r++, l++; // 转成 1-based
32
        return (h[r] - (1ll * h[l - 1] * p[r - l + 1] % MOD) + MOD) % MOD;
33
    }
34
};
35

36
Hash hx1(la1, p1, MOD1), hx2(la2, p2, MOD2), hy1(lb1, p1, MOD1),
37
    hy2(lb2, p2, MOD2);
38

39
int gcd(int a, int b) {
40
    if (b == 0)
41
        return a;
42
    return gcd(b, a % b);
43
}
44

45
signed main() {
46
    freopen("magic.in", "r", stdin);
47
    freopen("magic.out", "w", stdout);
48

49
    cin >> sx >> sy;
50
    hx1.init(sx), hx2.init(sx), hy1.init(sy), hy2.init(sy);
51
    int maxLen = gcd(sx.size(), sy.size());
52
    vector<int> fac;
53
    for (int i = 1; i <= sqrt(maxLen); i++) {
54
        if (maxLen % i == 0) {
55
            fac.push_back(i);
56
            if (i * i != maxLen) {
57
                fac.push_back(maxLen / i);
58
            }
59
        }
60
    }
61
    int ans = 0;
62
    for (int i = 0; i < fac.size(); i++) {
63
        int len = fac[i];
64
        // 判断是否是循环节
65
        if (!(hx1.get(0, sx.size() - len - 1) == hx1.get(len, sx.size() - 1) &&
66
              hx2.get(0, sx.size() - len - 1) == hx2.get(len, sx.size() - 1)))
67
            continue;
68

69
        if (!(hy1.get(0, sy.size() - len - 1) == hy1.get(len, sy.size() - 1) &&
70
              hy2.get(0, sy.size() - len - 1) == hy2.get(len, sy.size() - 1)))
71
            continue;
72

73
        // 判断循环节是否在两个子串中都相等
74
        if (!(hx1.get(0, len - 1) == hy1.get(0, len - 1) &&
75
              hx2.get(0, len - 1) == hy2.get(0, len - 1)))
76
            continue;
77
        ans++;
78
    }
79
    cout << ans;
80
}

一般的，对循环节的判断可以使用哈希轻松解决。

音乐

音乐

题目描述#

输入格式#

输出格式#

样例#

输入 #1#

输出 #1#

样例解释#

数据范围#

文章分享

音乐

安吉D3-T1

题目描述#

输入格式#

输出格式#

样例#

输入 #1#

输出 #1#

样例解释#

数据范围#

文章分享