HN的大爷们都太强了Orzzzzzzzz

懵逼的 题目

看不懂的 描述

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

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

总是输错的 读入

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

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

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

输了也WA的 输出

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

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

算不出的 样例

input

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

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$, 也就是第四个

扯淡的 题解

不会 这题不会

直接 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
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$的初始化和匹配是类似的过程…
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;
}

沙茶的 代码

#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