翻车笔记_ XIZ [KMP, 清奇脑回路]

HN的大爷们都太强了Orzzzzzzzz

懵逼的 题目

看不懂的 描述

给两个串(长度$n, m <= 10 ^ 6$), 字符集为$c <= 10 ^ 6$

每次可以钦定字符与字符的相等关系, 求最多有多少匹配, 并输出匹配的位置

总是输错的 读入

第一行两个数, 一个数据组数, 一个字符集的大小

每一组数据一行两个数, $m, n$, 代表字符串长度

一行$n$个数, 代表串$s$, 下一行$m$个数, 代表串$t$

输了也WA的 输出

一行一个整数$ans$代表$t$在$s$中能匹配的次数

一行$ans$个整数代表匹配的开头

算不出的 样例

input

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:

gg 1 2 3 4 5 6
S 0 0 2 2 0 2
T 0 0 2

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];
}
}
// 1 2 1 2 3 2
// 3 1 3
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;
}

/*
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
*/

By 跪烂大爷们的 Cansult