翻车笔记 XIZ [KMP, 清奇脑回路]
HN的大爷们都太强了Orzzzzzzzz
懵逼的 题目
看不懂的 描述
给两个串(长度\(n, m <= 10 ^ 6\)), 字符集为\(c <= 10 ^ 6\)
每次可以钦定字符与字符的相等关系, 求最多有多少匹配, 并输出匹配的位置
总是输错的 读入
第一行两个数, 一个数据组数, 一个字符集的大小
每一组数据一行两个数, \(m, n\), 代表字符串长度
一行\(n\)个数, 代表串\(s\), 下一行\(m\)个数, 代表串\(t\)
输了也WA的 输出
一行一个整数\(ans\)代表\(t\)在\(s\)中能匹配的次数
一行\(ans\)个整数代表匹配的开头
算不出的 样例
input
1 | 3 3 |
output
1 | 3 |
样例解释
题目太难懂了… 比如说串\(112121\), 和串\(313\)…
- 第一次匹配 我钦定 \(1 = 3, 2 = 1\), 所以匹配到了\(121\), 也就是第二个
- 第二次匹配 我钦定 \(2 = 3, 1 = 1\), 所以匹配到了\(212\), 也就是第三个
- 第三次匹配 我钦定 \(1 = 3, 2 = 1\), 所以匹配到了\(121\), 也就是第四个
扯淡的 题解
不会 这题不会
1 | 直接 hash 就可以了 ... |
考完看了看题解…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 | bool cmpa(const int dq, const int hsd) |
cmpb是用来做kmp匹配的, 基本和上面差不多…反正\(kmp\)的初始化和匹配是类似的过程…
1 | bool cmpb(const int dq, const int hsd) |
沙茶的 代码
1 |
|
By 跪烂大爷们的 Cansult