CF314B Sereja and Periods

题目大意:给定两个串 $s, t$ 和两个整数 $n, m$,设 $[s, n]$ 为串 $s$ 首尾相接拼接 $n$ 次而成。求最大的 $M$ 使得 $[[t, m], M]$ 为 $[s, n]$ 的子序列。

题解

首先,如果我们能找到最大的 $k$ 使得 $[t, k]$ 是 $[s, n]$ 的子序列,那么显然答案就是 $\lfloor \frac {k} {m}\rfloor$。于是我们把问题转化为寻找这样的 $k$。

其次,这样含有“重复”的问题似乎可以使用倍增处理。我们下面使用这种想法。

先预处理出 nxt 数组:(方便起见,下面的字符都用 025 之间的数表示)nxt[j][i] 表示字符串 sj 位置,最近的下一个 i 字符的位置。这里的下一个是循环移位的,即下一个字符可以存在于 j 之前的位置。如果 j 位置之后不存在 i 字符则为 -1

然后处理转移数组。endp[i][j] 表示从某个 si 位置开始和 $2^j$ 个前后拼接的 t 匹配,匹配完成的位置。这里的匹配可以看作是在由无限个 s 首尾拼接成的串上进行的。可以在 $O(|s||t|)$ 的时间内利用 nxt 数组计算出 endp[i][0],那么有 endp[i][j]=endp[endp[i][j-1]][j-1]

再处理总共需要多少个 s 完成这样的转移。cnt[i][j] 表示从 si 位置开始和 $2^j$ 个前后拼接的 t 匹配,中间经过的 s 的首尾相接处的个数。在计算 endp[i][0] 时可以顺便计算 cnt[i][0],然后有 cnt[i][j]=cnt[i][j-1]+cnt[endp[i][j-1]][j-1]

最后,我们使用 endp[i][j]cnt[i][j] 来计算结果。倍增过程和倍增求 LCA 类似,此处不赘述。

整个算法的时间复杂度为 $O(|s||t|+L|s|)$,这里的 $L$ 是倍增时选取的最大的 $2^j$ 的指数。这里选 $L=31$。

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
#include <bits/stdc++.h>
#define INF 2000000000
using namespace std;
typedef long long ll;
int read(){
int f = 1, x = 0;
char c = getchar();
while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
return f * x;
}
int endp[105][32], nxt[105][26];
ll cnt[105][32];
class Solution {
public:
int getMaxRepetitions(string s1, int n1, string s2, int n2) {
memset(endp, 0, sizeof(endp));
memset(cnt, 0, sizeof(cnt));
memset(nxt, -1, sizeof(nxt));
int l1 = s1.length(), l2 = s2.length();
for (int i = 0; i < 26; ++i){
int pos = -1;
for (int j = 0; j < l1; ++j)
if (s1[j] == i + 'a'){
pos = j;
break ;
}
if (pos < 0){
for (int j = 0; j < l1; ++j)
nxt[j][i] = -1;
}else {
nxt[pos][i] = pos;
for (int j = (pos == 0 ? l1 - 1: pos - 1), lst = pos; j != pos; lst = j, j = (j == 0 ? l1 - 1: j - 1)){
if (s1[j] == i + 'a') nxt[j][i] = j;
else nxt[j][i] = nxt[lst][i];
}
}
}
for (int i = 0; i < l2; ++i)
if (nxt[0][s2[i] - 'a'] < 0)
return 0;
for (int i = 0; i < l1; ++i) {
int cur = i;
for (int j = 0; j < l2; ++j){
int nx = nxt[cur][s2[j] - 'a'];
if (nx < cur) ++cnt[i][0];
if (nx == l1 - 1) cur = 0, ++cnt[i][0];
else cur = nx + 1;
}
endp[i][0] = cur;
}
for (int i = 1; i <= 31; ++i)
for (int j = 0; j < l1; ++j)
endp[j][i] = endp[endp[j][i - 1]][i - 1],
cnt[j][i] = cnt[j][i - 1] + cnt[endp[j][i - 1]][i - 1];
int ans = 0, used = 0, cur = 0;
for (int i = 31; i >= 0; --i)
if (cnt[cur][i] + used < n1 || (cnt[cur][i] + used == n1 && endp[cur][i] == 0))
used += cnt[cur][i], cur = endp[cur][i],
ans += (1 << i);
return ans / n2;
}
};
void init(){

}
void solve(){
int n1 = read(), n2 = read();
string s1, s2;
cin >> s1 >> s2;
Solution sol;
cout << sol.getMaxRepetitions(s1, n1, s2, n2) << endl;
}
int main(){
init();
solve();
return 0;
}