题集链接
OP
感谢学长的讲解与付出；
感谢ph和zsl两位大佬的指导与讨论；
KMP可以在线性复杂度内求出给定字符串任意前 i 个元素构成字串的最长相等前后缀，并可以以此进一步进行字串匹配或其他相等前后缀的求取；
A 剪花布条
题目大意
给定待测串和标准串，求待测串中有几个互不重复的标准串；
思路
KMP字串匹配板，KMP本身即是求取互不重复的标准串个数；
代码
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
| #include <stdio.h>
#include <iostream>
#include <stack>
#include <vector>
#include <algorithm>
#include <string.h>
using namespace std;
#pragma GCC optimize(2)
typedef long long ll;
typedef int itn;
typedef unsigned long long ull;
char A[1010],B[1010];
int nxt[1010],n,m,ans;
void pre()
{
nxt[1]=0;
int j=0;
for(int i=1;i<m;i++)
{
while(j>0&&B[j+1]!=B[i+1])
{
j=nxt[j];
}
if(B[j+1]==B[i+1])j++;
nxt[i+1]=j;
}
}
void kmp()
{
int j=0;
for(int i=0;i<n;i++)
{
while(j>0&&B[j+1]!=A[i+1])
{
j=nxt[j];
}
if(B[j+1]==A[i+1])j++;
if(j==m)
{
ans++;
j=0;
}
}
}
int main()
{
while(cin>>A+1)
{
if(!strcmp(A+1,"#"))break;
cin>>B+1;
n=strlen(A+1);
m=strlen(B+1);
ans=0;
pre();
kmp();
printf("%d\n",ans);
}
}
|
B Power Strings
题目大意
给定串是由几个相同字符串首尾相接拼出来的，求出最大个数；
思路
我们先分情况讨论：
假定给定串长度为 m ；
- 2⋅nxt[m]<m ，此时显然没有满足条件的串，故答案为1；
- 2⋅nxt[m]⩾m ，此时可能的串是 [1,m−nxt[m]] ，即可以保证给定串是若干个可行串首尾相接组成串的前缀，下一步只需要判断给定串与可行串长度有没有整除关系即可；
接下来对两种情况进行合并，满足第一种情况时，两串长度一定不存在整除关系；
代码
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
| #include <stdio.h>
#include <iostream>
#include <stack>
#include <vector>
#include <algorithm>
#include <string.h>
#include <math.h>
using namespace std;
#pragma GCC optimize(2)
typedef long long ll;
typedef int itn;
typedef unsigned long long ull;
char A[1010], B[1000006];
int nxt[1000006], n, m, ans;
void pre()
{
nxt[1] = 0;
int j = 0;
for (int i = 1; i < m; i++)
{
while (j > 0 && B[j + 1] != B[i + 1])
{
j = nxt[j];
}
if (B[j + 1] == B[i + 1])
j++;
nxt[i + 1] = j;
}
}
void kmp()
{
int j = 0;
for (int i = 0; i < n; i++)
{
while (j > 0 && B[j + 1] != A[i + 1])
{
j = nxt[j];
}
if (B[j + 1] == A[i + 1])
j++;
if (j == m)
{
ans++;
j = 0;
}
}
}
int main()
{
while (~scanf("%s",B+1))
{
if(!strcmp(B+1,"."))break;
m = strlen(B + 1);
pre();
printf("%d\n", (m%(m - nxt[m])==0)?m/(m - nxt[m]):1);
}
}
|
C Radio Transmission
题目大意
给你一个字符串，它是由某个字符串不断自我连接形成的。但是这个字符串是不确定的，现在只想知道它的最短长度是多少。
思路
和上一题基本相同，求出可行串长度即可；
代码
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
| #include <stdio.h>
#include <iostream>
#include <stack>
#include <vector>
#include <algorithm>
#include <string.h>
using namespace std;
#pragma GCC optimize(2)
typedef long long ll;
typedef int itn;
typedef unsigned long long ull;
char A[1010],B[1000006];
int nxt[1000006],n,m,ans;
void pre()
{
nxt[1]=0;
int j=0;
for(int i=1;i<m;i++)
{
while(j>0&&B[j+1]!=B[i+1])
{
j=nxt[j];
}
if(B[j+1]==B[i+1])j++;
nxt[i+1]=j;
}
}
void kmp()
{
int j=0;
for(int i=0;i<n;i++)
{
while(j>0&&B[j+1]!=A[i+1])
{
j=nxt[j];
}
if(B[j+1]==A[i+1])j++;
if(j==m)
{
ans++;
j=0;
}
}
}
int main()
{
cin>>m;
cin>>B+1;
pre();
printf("%d",m-nxt[m]);
}
|
D OKR-Periods of Words
参考
题目大意
对于给定的字符串t，找到它所有前缀字串的最长周期的长度的和。
思路
根据题目中周期的定义，我们只需要求出每个串的最短相同前后缀的长度，总长减去该长度即为该串的周期长；
同时需要用路径压缩优化；
代码
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
| #include <stdio.h>
#include <iostream>
#include <stack>
#include <vector>
#include <algorithm>
#include <string.h>
#include <math.h>
using namespace std;
#pragma GCC optimize(2)
typedef long long ll;
typedef int itn;
typedef unsigned long long ull;
char A[1010], B[1000006];
int nxt[1000006], n, m, ans;
void pre()
{
nxt[1] = 0;
int j = 0;
for (int i = 1; i < m; i++)
{
while (j > 0 && B[j + 1] != B[i + 1])
{
j = nxt[j];
}
if (B[j + 1] == B[i + 1])
j++;
nxt[i + 1] = j;
}
}
void kmp()
{
int j = 0;
for (int i = 0; i < n; i++)
{
while (j > 0 && B[j + 1] != A[i + 1])
{
j = nxt[j];
}
if (B[j + 1] == A[i + 1])
j++;
if (j == m)
{
ans++;
j = 0;
}
}
}
int main()
{
cin>>m;
cin>>B+1;
pre();
ll ans=0;
for(int i=1;i<=m;i++)
{
int now=i;
while(nxt[now])now=nxt[now];
if(nxt[i])nxt[i]=now;
ans+=i-now;
}
cout<<ans;
}
|
E 似乎在梦中见过的样子
题目大意
所有形似于 A+B+A 的字串都是 QB 或它的替身，且 |A|≥k,|B|≥1 （位置不同其他性质相同的子串算不同子串，位置相同但拆分不同的子串算同一子串），对于给定串和给定 k ，求出其替身数量；
思路
实际上是 O(n2) 复杂度；
对于每一个后缀串进行kmp，并遍历每个后缀串的所有前缀，以遍历所有字串；
对于每个子串，假设其某相等前后缀长度为 h ，字串长度为 l，找到其是否有同时满足 h⩾k,2⋅h+1⩽l 的相等前后缀；
代码
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
| #include <stdio.h>
#include <iostream>
#include <stack>
#include <vector>
#include <algorithm>
#include <string.h>
#include <math.h>
using namespace std;
#pragma GCC optimize(2)
typedef long long ll;
typedef int itn;
typedef unsigned long long ull;
char A[1010], B[1000006];
int nxt[1000006], n, m, ans;
void pre()
{
nxt[1] = 0;
int j = 0;
for (int i = 1; i < m; i++)
{
while (j > 0 && B[j + 1] != B[i + 1])
{
j = nxt[j];
}
if (B[j + 1] == B[i + 1])
j++;
nxt[i + 1] = j;
}
}
void kmp()
{
int j = 0;
for (int i = 0; i < n; i++)
{
while (j > 0 && B[j + 1] != A[i + 1])
{
j = nxt[j];
}
if (B[j + 1] == A[i + 1])
j++;
if (j == m)
{
ans++;
j = 0;
}
}
}
int main()
{
cin >> B + 1;
m = strlen(B + 1);
int k;
cin >> k;
ll ans = 0;
for (; m >= 2 * k + 1; m--)
{
pre();
for (int i = 1; i <= m; i++)
{
B[i] = B[i + 1];
int now = i;
while (nxt[now] >= k)
{
if (2 * nxt[now] + 1 <= i)
{
ans++;
break;
}
now = nxt[now];
}
}
}
cout << ans;
}
|
F Censoring
题目大意
给出两个字符串 S 和 T，每次从前往后找到 S 的一个子串 A=T 并将其删除，空缺位依次向前补齐，重复上述操作多次，直到 S 串中不含 T 串。输出最终的 S 串。
思路
最终用数组模拟栈和字符串哈希完成的；
持续对比栈的后缀和下一个字符串前缀的哈希值，如果有相等的，则将栈顶的重合元素弹出；
代码
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
| #include <stdio.h>
#include <iostream>
#include <stack>
#include <vector>
#include <algorithm>
#include <string.h>
#include <math.h>
using namespace std;
typedef long long ll;
typedef int itn;
typedef unsigned long long ull;
const int N = 1e6 + 6;
const ll mod = 1e9 + 3, base = 1321;
int s[N], p[N] = {1}, tmp;
int top, len;
char a[N], b[N], c[N];
ll get(int l, int r) { return ((ll)s[r] - (ll)s[l - 1] * p[r - l + 1] + mod*mod) % mod; }
int main()
{
for (int i = 1; i < N; i++)
p[i] = (ll)p[i - 1] * base % mod;
cin >> a + 1;
cin >> b + 1;
for (int i = 1; b[i]; i++)
tmp = (tmp * base + b[i]) % mod, len++;
for (int i = 1; a[i]; i++)
{
s[top + 1] = (s[top] * base + a[i]) % mod;
c[++top] = a[i];
if (top >= len && get(top - len + 1, top) == tmp)
top = top - len;
}
for (int i = 1; i <= top; i++)
printf("%c", c[i]);
return 0;
}
|
G Compress Words
题目大意
样例解释得很明白，不过要强调一点：即先合并前两个单词，然后将结果与第三个单词合并，依此类推
思路
维护ans串；
对于每个新单词，截取ans串的适当后缀和该新单词组成临时串，对临时串kmp，判断是否公共前后缀，该缀即为重复部分；
有时候公共前后缀的长度可能超过预期，此时即需要特判；
代码
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 <stdio.h>
#include <iostream>
#include <stack>
#include <vector>
#include <algorithm>
#include <string.h>
#include <math.h>
using namespace std;
#pragma GCC optimize(2)
typedef long long ll;
typedef int itn;
typedef unsigned long long ull;
string A,B;
int nxt[1000006], n, m;
void pre()
{
nxt[1] = 0;
int j = 0;
for (int i = 1; i < m; i++)
{
while (j > 0 && B[j + 1] != B[i + 1])
{
j = nxt[j];
}
if (B[j + 1] == B[i + 1])
j++;
nxt[i + 1] = j;
}
}
void kmp()
{
int j = 0;
for (int i = 0; i < n; i++)
{
while (j > 0 && B[j + 1] != A[i + 1])
{
j = nxt[j];
}
if (B[j + 1] == A[i + 1])
j++;
if (j == m)
{
j = 0;
}
}
}
string g[100005],ans;
int main()
{
int k;
cin>>k;
for(int i=1;i<=k;i++)cin>>g[i];
ans=g[1];
for(int i=2;i<=k;i++)
{
B=' '+g[i]+ans.substr(max(0,(int)(ans.length()-g[i].length())));
m=B.length()-1;
pre();
int now=m;
while(nxt[now]>min(ans.length(),g[i].length())&&nxt[m])now=nxt[now];
ans+=g[i].substr(nxt[now]);
}
cout << ans;
}
|
H 动物园
思路
这道题比较像E的单次循环，但是E的数据非常水，导致O(n2)+暴力递归也能过；
这道题卡得就比较严了，需要更优的策略；
定义nx[i]为长度小于等于i/2的最长公共前后缀；
如果要求取nx[i]，我们可以按照求取next[i]的类似思路进行，只不过最后判断是否大于i/2即可；
那么还需要求取的是num[i]；
如果next[i]=j，那么显然num[i]=num[j]+1；
在计算ans时，我们需要乘上num[nx[i]]+1；
由于nx值的缩减过程也是按照next迭代的，所以在下面代码中，上文的nx没有被存下；
此外next为nx，num为sz；
代码中，sz[i]代表i长度的公共前后缀内的公共前后缀数+1，即nx[i]=j时，num[i]=sz[j]；
代码
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
| #include <iostream>
#include <algorithm>
#include <string.h>
#include <math.h>
#include <map>
#include <vector>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int N = 1e6+6;
const int M = 1e9 + 7;
int n;
int nt[N], sz[N];
char a[N];
int main()
{
int t;
cin >> t;
while (t--)
{
ll ans = 1;
scanf("%s", a + 1);
int n = strlen(a + 1);
sz[1]=1;
for (int i = 2, j = 0; i <= n; i++) {
while (j && a[i] != a[j + 1]) j = nt[j];
if (a[i] == a[j + 1]) j++;
nt[i] = j;
sz[i] = sz[nt[i]] + 1;
}
for (int i = 1, j = 0; i <= n; i++) {
while (j && a[j + 1] != a[i]) j = nt[j];
if (a[j + 1] == a[i]) j++;
while (j * 2 > i) j = nt[j];
ans = ans * (sz[j] + 1) % M;
}
printf("%lld\n", ans);
}
}
|
I Sza-Template
KMP+DP
思路
参考
假设f(i)为给定串长度为 i 的前缀的答案；
则有f(i)=i或f[nx[i]]，具体证明详见上链；
在存在 j 满足f(j)=f(nx[i])且j+nx[i]⩽i时，f(i)=f(nx[i])；
具体判断可以用桶实现；
代码
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
| #include <iostream>
#include <algorithm>
#include <string.h>
#include <math.h>
#include <map>
#include <vector>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int N = 5e5+5;
const int M = 998244353;
int n;
int nx[N];
int f[N],h[N];
char s[N];
int main()
{
scanf("%s",s+1); n=strlen(s+1);
nx[0]=-1;
for(int i=2,j=0; i<=n; ++i)
{
while(j!=-1&&s[j+1]!=s[i]) j=nx[j];
nx[i]=++j;
}
f[1]=1;
for(int i=2; i<=n; ++i)
{
f[i]=i;
if(h[f[nx[i]]]>=i-nx[i]) f[i]=f[nx[i]];
h[f[i]]=i;
}
printf("%d",f[n]);
}
|
ED
\