CF149 E Martian Strings

CF149 E Martian Strings

CF149 E Martian Strings

题意翻译

输入第一行给定一个长度为 $n$ $(1\leq n \leq 1e5)$ 的字符串 $s$,该串仅由大写字母组成

第二行给定一个数 $m\ \ (1 \leq m \leq 100)$,接下来 $m$ 行表示 $m$ 个询问

每行一个字符串 $p_i$ $(1 \leq |p_i| \leq 1000)$,满足$p_i$互不相同。

一个询问 $p_i$可行当且仅当存在 $a,b,c,d$满足$1\leq a\leq b \lt c \leq d \leq n$且$ s_as_{a+1}\dots s_{b}s_{c}s_{c+1}\dots s_d = p_i$

即可以找到两个不相交的区间,满足这两个区间对应的子串拼起来和 $p_i$相同

输出一行表示可行的询问的数量

思路

先正向$kmp$,记录$T$的前缀的每一个长度,在$S$能匹配的最左边,也就是首次匹配的位置(指最后一位)

然后就是把寻找后缀,把$S$和$T$都逆序存好,再$kmp$一次

看是否可以找到一个长度为$x$的后缀的位置在一个长度为$len-x$的前缀的位置之后,如果可以找到就是合法的

题解代码

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
#include <cstdio>
#include <cmath>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <set>
#define LL long long
const int inf = 1e9 + 9;
const int N = 2e5 + 5;
using namespace std;
char s[N], t[N], c[N];
int a[N], nxt[N];
void next(char x[], int f[]) //板子
{
int m = strlen(x);
f[0] = f[1] = 0;
for (int i = 1; i < m; i++)
{
int j = f[i];
while (j && x[i] != x[j])
j = f[j];
f[i + 1] = x[i] == x[j] ? 1 + j : 0;
}
/*
for (int i = 0; i <= m; i++)
printf("%d:%d ", i, f[i]);
printf("\n");
*/
}
bool find(char s[], char t[], int f[], int v)
{
next(t, f); //kmp的一种模板
int n = strlen(s), m = strlen(t), j = 0;
for (int i = 0; i < n; i++)
{
while (j && s[i] != t[j])
j = f[j];
if (s[i] == t[j])
++j;
if (v == 1 && j && a[j] == -1)
a[j] = i;//正向的时候,用把第一个前缀为j的最后一个位置i存进数组a[j]里
/*
目前是反向,由于目前的前缀的长度是j,也就是原串的后缀长度目前是j
所以先要确认之前正向的时候标记的长度是m-j的前缀存不存在
然后要确认位置,因为这两个区间不能重合
*/
if (v == 2 && j && a[m - j] != -1 && a[m - j] < n - i - 1)
return 1;
//只要成立一个就可以了
}
return 0;
}
void back(char s[], int n) //一个简单的倒置
{
char ch;
for (int i = 0, k = n - 1; i < n / 2; i++, k--)
{
ch = s[i];
s[i] = s[k];
s[k] = ch;
}
}
int main()
{
scanf("%s", s);
int m, cnt = 0;
scanf("%d", &m);
while (m--)
{
scanf("%s", t);
memset(a, -1, sizeof(a)); //全初始化为-1
find(s, t, nxt, 1); //正向匹配
int n = strlen(s);
for (int i = n - 1, k = 0; i >= 0; i--) //把s倒过来,由于下次还要用,所以不能用back函数
c[k++] = s[i];
back(t, strlen(t)); //把t倒过来
if (find(c, t, nxt, 2)) //反向kmp去找符合的情况,如果存在就加一
cnt++;
}
printf("%d\n", cnt);
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
void next(char x[], int f[]) //板子
{
int m = strlen(x);
f[0] = f[1] = 0;
for (int i = 1; i < m; i++)
{
int j = f[i];
while (j && x[i] != x[j])
j = f[j];
f[i + 1] = x[i] == x[j] ? 1 + j : 0;
}
/*
for (int i = 0; i <= m; i++)
printf("%d:%d ", i, f[i]);
printf("\n");
*/
}
/*
怎么去理解这个板子呢?
先带入样例去看看它是怎么跑的
ABCBABA
2
BAAB
ABBA

BAAB\ABBA 一样的
f[1]=f[0]=0

j=f[1]=0
x[1]=A,x[0]=B
f[2]=0

j=f[2]=0
x[2]=A,x[0]=B
f[3]=0

j=f[3]=0
x[3]=A,x[0]=A
f[4]=1

最后我们可以得到f[4]=1,其它都是等于0
f[4]=1的意思就是ABBA成立,下一个成立的是ABBABBA
f[1]=0也就是ABBABBA成立,下一个成立的是ABBAABBA
所以next函数将字符串从最大前缀开始向下搜,确保我们能得到符合条件内最大前缀长度
*/