CF1090 J Two Prefixes

CF1090 J Two Prefixes

CF1090 J Two Prefixes

题意

给两个字符串,问两个非空前缀拼成的字符串最多有多少种

思路

只需要考虑重复的就行

考虑相同的$s = ab$我们用长度最长的$a$作为代表串

对$b$求$kmp$,然后我们在考虑$b$的一段前缀在$a$中出现的次数

这个出现的次数很明显就是重复了多少次了

题解代码

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
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e5 + 5;
char ch[N], s[N], t[N];
int f[N], g[N], ans[N];
void kmp(int n)
{
for (int i = 2; i <= n; i++)
{
f[i] = f[i - 1];
while (f[i] && ch[f[i] + 1] != ch[i])
f[i] = f[f[i]];
f[i] = (ch[f[i] + 1] == ch[i] ? f[i] + 1 : f[i]);
}
}
void exkmp(int n)
{
int ms = 1;
for (int i = 2; i <= n; i++)
{
g[i] = max(0, min(g[i - ms + 1], ms + g[ms] - i));
while (i + g[i] <= n && ch[i + g[i]] == ch[1 + g[i]])
g[i]++;
if (i + g[i] > ms + g[ms])
ms = i;
}
g[1] = n;
}
int main()
{
while (1)
{
scanf("%s%s", t + 1, s + 1);
int n = strlen(s + 1);
memcpy(ch + 1, s + 1, sizeof(char) * (n));
kmp(n);
/*
printf("ch:%s\n", ch + 1);
for (int i = 0; i <= n; i++)
printf("f[%d]:%d ", i, f[i]);
printf("\n");
*/
int ls = n, lt = strlen(t + 1);
ch[++n] = '*';
for (int i = 1; i <= lt; i++)
ch[++n] = t[i];
exkmp(n);
/*
printf("ch:%s\n", ch + 1);
for (int i = 0; i <= n; i++)
printf("g[%d]:%d ", i, g[i]);
printf("\n");
*/
for (int i = ls + 3; i <= n; i++)
ans[g[i]]++;
for (int i = ls; i >= 1; i--)
ans[i] += ans[i + 1];
ll fin = 1ll * lt * ls;
for (int i = 1; i <= ls; i++)
if (f[i])//如果存在前缀
fin -= ans[i - f[i]];//减去所有重合
printf("%I64d\n", fin);
}

return 0;
}

重点解析

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
void exkmp(int n)
{
int ms = 1;
for (int i = 2; i <= n; i++)
{
g[i] = max(0, min(g[i - ms + 1], ms + g[ms] - i));
while (i + g[i] <= n && ch[i + g[i]] == ch[1 + g[i]])
g[i]++;
if (i + g[i] > ms + g[ms])
ms = i;
}
g[1] = n;
}
/*
手动模拟跑一次就好了
input:
aba
aa
output:
5

kmp处理出s串的f数组
f[0]:0 f[1]:0 f[2]:1

然后两个字符串拼接
aa*aba

ms=1
g[2]=max(0,min(g[2-1+1],1+g[1]-2))
g[2]=max(0,min(g[2],g[1]-1))
g[2]=max(0,min(0,-1))
g[2]=0
2+g[2]<=6 && ch[2+0] == ch[1+0]
g[2]=1
2+g[2]>1+g[1]

ms=2
g[3]=max(0,min(g[3-2+1],2+g[2]-3))
g[3]=max(0,min(g[2],g[2]-1))
g[3]=0
3+g[3]<=6 && ch[3+0] == ch[2+0]
3+g[3]>2+g[2]

ms=2
g[4]=max(0,min(g[4-2+1],2+g[2]-4))
g[4]=max(0,min(g[3],g[2]-2))
g[4]=0
4+g[4]<=6 && ch[4+0] == ch[1+0]
g[4]=1
4+g[4]>2+g[2]

ms=4
g[5]=max(0,min(g[5-4+1],4+g[4]-5))
g[5]=max(0,min(g[2],g[4]-1))
g[5]=0
5+g[5]<=6 && ch[5+g[5]] == ch[1+g[5]]
5+g[5]>4+g[4]

ms=4
g[6]=max(0,min(g[6-4+1],4+g[4]-6))
g[6]=max(0,min(g[3],g[4]-1))
g[6]=0
6+g[6]<=6 && ch[6+0] == ch[1+g[i]]
g[6]=1

g[1]=6

最后得到
g[0]:0 g[1]:6 g[2]:1 g[3]:0 g[4]:1 g[5]:0 g[6]:1

for (int i = ls + 3; i <= n; i++)
ans[g[i]]++;
for (int i = ls; i >= 1; i--)
ans[i] += ans[i + 1];
ans[g[5]]
ans[0]=1

ans[g[6]]
ans[1]=1

ans[2]=0
ans[1]=1

for (int i = 1; i <= ls; i++)
if (f[i])
fin -= ans[i - f[i]];
-ans[2-f[2]]=-ans[1]
*/
//TODO