Tavas and Malekas

Tavas and Malekas

Tavas and Malekas

题意

给你一个子串$p$,且在长度为$n$的原串中出现的$m$个插入位,问原串有几种可能

https://acm.njupt.edu.cn/contest/123/board/challenge/G

思路

首先对字符串$p$做一次$kmp$

然后对原串一个个插入

如果没有冲突,填完后剩下部分的空,每个都能填$26$个字母,$mod$后输出就行

解析见注释

代码部分

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
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 1e6 + 7;
const int MOD = 1e9 + 7;
typedef long long LL;
char s[maxn];
int N, M, a[maxn], nt[maxn];
char p[maxn];
bool vis[maxn], vis1[maxn];
void getnext(char *s, int len)//函数解析见重点解析
{
nt[0] = -1;
int i = 0, j = -1;
while (i < len)
{
if (j == -1 || s[i] == s[j])
{
i++, j++;
nt[i] = j;
}
else
j = nt[j];
}
int r = len;
while (r != -1)
{
vis1[r] = 1;
r = nt[r];
}
}
int main()
{
scanf("%d%d", &N, &M);
scanf("%s", s);
int len = strlen(s);
getnext(s, len);
for (int i = 1; i <= M; i++)
scanf("%d", &a[i]);
sort(a + 1, a + 1 + M);
for (int i = 1; i <= M; i++)
{
if (i == 1 || a[i] - a[i - 1] >= len)
{
for (int j = a[i]; j < a[i] + len; j++) //标记为占用
vis[j] = 1;
}
else //如果发生冲突
{
if (vis1[a[i - 1] + len - a[i]]) //a[i-1]的后缀和a[i]的前缀重叠
{
for (int j = a[i - 1] + len; j < a[i] + len; j++) //然后对这部分打标记
vis[j] = 1;
}
else //冲突了,这个字符串无法构成,直接输出零就行
{
printf("0\n");
return 0;
}
}
}
LL cnt = 1;
for (int i = 1; i <= N; i++) //剩下的空26个字母都可以填
if (!vis[i])
cnt = (cnt * 26) % MOD;
cout << cnt << endl;
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
void getnext(char *s, int len)//对这个函数,带入样例IOI看一下结果
{
nt[0] = -1;
int i = 0, j = -1;
while (i < len)
{
if (j == -1 || s[i] == s[j])
{
i++, j++;
nt[i] = j;
}
else
j = nt[j];
}
int r = len;
while (r != -1)
{
vis1[r] = 1;
r = nt[r];
}
}
/*
运行逻辑如下
IOI

nt[0] = -1
i = 0,j = -1
//以上为初始化
i = 1, j = 0
nt[1] = 0

s[1] = o,s[0] = i
j = nt[0] = -1
i = 2,j = 0
nt[2] = 0

s[2] = i,s[0] = i
i = 3,j = 1
nt[3] = 1 //跳出

r = 3 //由于下标从0开始,所以len绝对成立
v1[3] = 1

r = nt[3] = 1
v1[1] = 1

r = nt[1] = 0
v1[0] = 1

r = -1 //跳出
*/

/*
可以得到v1数组的0,1,3下标被标记了
这个0的意思是IOIIOI成立,也就是前一个S和后一个S相交字符为0个
这个1的意思是IOIOI成立,也就是前一个S和后一个S相交字符为1个
这个3的意思是IOI成立,也就是前一个S和后一个S相交字符为3个
*/