HN的大爷们都太强了Orzzzzzzzz
懵逼的 题目
看不懂的 描述
给两个串(长度\(n, m <= 10 ^ 6\)),
字符集为\(c <= 10 ^ 6\)
每次可以钦定字符与字符的相等关系, 求最多有多少匹配,
并输出匹配的位置
总是输错的 读入
第一行两个数, 一个数据组数, 一个字符集的大小
每一组数据一行两个数, \(m, n\),
代表字符串长度
一行\(n\)个数, 代表串\(s\), 下一行\(m\)个数, 代表串\(t\)
输了也WA的 输出
一行一个整数\(ans\)代表\(t\)在\(s\)中能匹配的次数
一行\(ans\)个整数代表匹配的开头
算不出的 样例
1
2
3
4
5
6
7
8
9
10
| 3 3
6 3
1 2 1 2 3 2
3 1 3
6 3
1 2 1 2 1 2
3 1 3
6 3
1 1 2 1 2 1
3 1 3
|
output
1
2
3
4
5
6
| 3
1 2 4
4
1 2 3 4
3
2 3 4
|
样例解释
题目太难懂了... 比如说串\(112121\),
和串\(313\)...
- 第一次匹配 我钦定 \(1 = 3, 2 = 1\),
所以匹配到了\(121\), 也就是第二个
- 第二次匹配 我钦定 \(2 = 3, 1 = 1\),
所以匹配到了\(212\), 也就是第三个
- 第三次匹配 我钦定 \(1 = 3, 2 = 1\),
所以匹配到了\(121\), 也就是第四个
扯淡的 题解
不会 这题不会
1
2
| 直接 hash 就可以了 ...
优美一点的做法是 KMP. 记每个字符的前一个字符距离自己的距离为 w_i, 如果两个串的 w 数组相等, 则可以匹配. 预处理出 w 就可以用 KMP 了.
|
考完看了看题解...Emmmmm好像很有趣...
然后写写写...发现...woc怎么样例不对啊...
按照题解预处理样例第一组的w:
woc这匹配个卵啊(摔!
尝试搞了一波比较函数 把超过当前匹配的长度的\(S\)的\(w\)值置为\(0\)
然后发现...\(w\)初始化时候的比较\(gg\)了...
然后问学长 + 参悟代码(感谢\(K404-A2\)的代码)...
Emmmmmm妙啊...写两个比较函数不就行了...
dq代表当前在匹配的位置,
hsd代表当前已经匹配上的位数,
lt[i]代表t串中位置i前最靠近的t[i]的位置,
ls[i]就是s中在i前最靠近s[i]的位置
cmpa函数是用来初始化fail数组的
- 第一个
if:
如果dq位置的w超出了当前匹配的位数,
而且当前的长度内没有重复的字符, 也就是不会对当前的串匹配产生影响,
返回true
- 第二个
if:
如果dq位置的w在当前匹配的位数内,
而且当前匹配的位数内也有t[hsd]重复出现, 返回他们是否相等,
即他们的w值是否相等
- 否则 一个出现了, 一个没有出现, 返回
false
1
2
3
4
5
6
7
8
| bool cmpa(const int dq, const int hsd)
{
if (t[dq] <= dq - hsd && !t[hsd])
return true;
if (t[dq] > dq - hsd && t[hsd])
return (dq - t[dq] == hsd - t[hsd]);
return false;
}
|
cmpb是用来做kmp匹配的, 基本和上面差不多...反正\(kmp\)的初始化和匹配是类似的过程...
1
2
3
4
5
6
7
8
| bool cmpb(const int dq, const int hsd)
{
if (s[dq] <= dq - hsd && !t[hsd])
return true;
if (s[dq] > dq - hsd && t[hsd])
return (dq - s[dq] == hsd - t[hsd]);
return false;
}
|
沙茶的 代码
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
90
91
92
93
94
95
96
97
98
| #include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define MAXN (1000000 + 5)
using namespace std;
int n, m, s[MAXN], t[MAXN], ls[MAXN], lt[MAXN], ans[MAXN], f[MAXN];
bool cmpa(int, int);
bool cmpb(int, int);
void init();
void kmp();
int main()
{
freopen("xiz.in", "r", stdin);
freopen("xiz.out", "w", stdout);
int tim, c;
scanf("%d%d", &tim, &c);
while (tim--)
{
memset(ls, 0, sizeof(ls));
memset(lt, 0, sizeof(lt));
memset(ans, 0, sizeof(ans));
scanf("%d%d", &n, &m);
int srx;
for (int i = 1; i <= n; i++)
{
scanf("%d", &srx);
s[i] = ls[srx], ls[srx] = i;
}
for (int i = 1; i <= m; i++)
{
scanf("%d", &srx);
t[i] = lt[srx], lt[srx] = i;
}
init();
kmp();
printf("%d\n", ans[0]);
for (int i = 1; i <= ans[0]; i++)
printf("%d ", ans[i]);
puts("");
}
return 0;
}
void init()
{
f[1] = f[2] = 1;
int j;
for (int i = 2; i <= m; i++)
{
j = f[i];
while (j != 1 && !cmpa(i, j)) j = f[j];
f[i + 1] = (cmpa(i, j) ? (j + 1) : 1);
}
}
void kmp()
{
int j = 1;
for (int i = 1; i <= n; i++)
{
while (j != 1 && !cmpb(i, j)) j = f[j];
if (cmpb(i, j))
++j;
if (j == m + 1)
ans[++ans[0]] = i - m + 1, j = f[j];
}
}
bool cmpa(const int dq, const int hsd)
{
if (t[dq] <= dq - hsd && !t[hsd])
return true;
if (t[dq] > dq - hsd && t[hsd])
return (dq - t[dq] == hsd - t[hsd]);
return false;
}
bool cmpb(const int dq, const int hsd)
{
if (s[dq] <= dq - hsd && !t[hsd])
return true;
if (s[dq] > dq - hsd && t[hsd])
return (dq - s[dq] == hsd - t[hsd]);
return false;
}
|
By 跪烂大爷们的 Cansult