字符串匹配

Posted on Edited on In

题目大意：对于一个字符集大小为\(C\)的字符串\(P\)，我们可以将任意两种字符在\(P\)中的位置进行交换，例如\(P\)=\(abcba\)，我们交换\(a,b\)就变为了\(bacab\)，交换\(a,d\)就变为了\(dbcbd\)，交换可以进行任意多次。若交换后\(P\)变为了字符串\(Q\)，则我们称字符串\(Q\)和\(P\)为匹配的现在给定两个字符集的大小为\(C\)的字符串\(S,T\)，请你求出\(S\)中有多少个连续子串与\(T\)匹配

考虑KMP的本质，是对完全相同的字符串进行匹配，而我们这里呢是对相对位置的匹配

将要求改为两个字符上一次出现的相对位置相同 (即位置差值) 即可

考察知识点：KMP的转化

不难，考场上应该想出来，但是心态爆炸了，没想到

代码如下：

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
#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 66;

int n, m, t;
int a[N], b[N];
int nex[N], xa[N], xb[N], f[N], q[N];

inline void pres_dou()
{
    n = read(), m = read();
    memset(nex, 0, sizeof nex);
    for (int i = 1; i <= n; ++ i)
    {
        a[i] = read();
        xa[i] = i - nex[a[i]], nex[a[i]] = i;
    }
    memset(nex, 0, sizeof nex);
    for (int i = 1; i <= m; ++ i)
    {
        b[i] = read();
        xb[i] = i - nex[b[i]], nex[b[i]] = i;
    }
    return;
}

inline void solve()
{
    t = xb[m + 1] = 0; int j = 0;
    for (int i = 2; i <= m; ++ i)
    {
        while (j && min(j + 1, xb[i]) != xb[j + 1]) j = f[j];
        if (min(j + 1, xb[i]) == xb[j + 1]) ++ j;
        f[i] = j;
    }
    j = 0;
    for (int i = 1; i <= n; ++ i)
    {
        while (j && min(j + 1, xa[i]) != xb[j + 1]) j = f[j];
        if (min(j + 1, xa[i]) == xb[j + 1]) ++ j;
        if (j == m) q[++ t] = i;
    }
    put(t);
    for (int i = 1; i <= t; ++ i) printf ("%d ", q[i] - m + 1); puts("");
    return;
}

signed main()
{
    
    int T = read(), C = read();
    while (T --) pres_dou(), solve();
    
    return 0;
}