kmp、差分约束

题意：

分析

第一个要突破的点在于：如何表示认错树木的现象。
我们可以暴力地枚举记忆中的p字符串，然后再用kmp进行匹配
但是很明显这会超时！
所以我们需要采取其他的办法。进行分辨。

这里我们使用的技巧叫做差分约束！
通过记录当前p[i]出现的位置与其上一次出现位置的差值，来限制数目的种类。
记录前后出现的差值。第一次出现则为0

然后在这种情况下进行kmp匹配.得出答案。

但是，差分约束也有一个问题：
如：
s = [0,0,2,2,2,2]
p = [0,0,2,2]
我们可以发现很明显s[0:4]==p[0:4]
但是其实s[2:6]==p[0:4]
因为，根据s[4]==2（索引从0开始）
s[2]==s[4]同理s[3]==s[5]
而p[0]=p[2],p[1]==p[3]
因此，是匹配的！！！

这种情况我们怎么区分呢？
我们发现，其实特殊的只有s[2]和s[3]

即第一次出现的时候，这是理所当然的。之后出现的都是与之前出现的差值。所以匹配条件一定是s[i]==p[j]
但是，第一次出现时应进行特殊判断！

其实，我们所要哦判断的就是，对于s[i]!=0的一个数。
我们如何判断在我们以匹配的p[0:j]中
他代表的字符是第一次出现还是已经出现过了。

其实只需判断s[i]是否大于j就可以了。
因为如果大于j那么意味着，s[i]与其上一次出现的距离超过了已经匹配的长度。
那么自然时第一次出现了。这时我们只要看p[j]是否为0.因为此时s[i]就相当于0啊

故，kmp算法中的判断条件不再是s[i]==p[j]而是s[i]<=j?s[i]==p[j]:p[j]==0
getnext也是一样的
如此，此题得解

代码如下

#include<iostream>
#include<algorithm>
using namespace std;
const int max_n = 2e5 + 100;
const int max_m = 1e5 + 100;
const int max_k = 12;
inline int read() {
    char c = getchar();
    int x = 0, f = 1;
    while (!isdigit(c)) { if (c == '-')f = -1;c = getchar(); }
    while (isdigit(c))x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
    return x * f;
}
inline void write(int x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    if (x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
    return;
}
int n, k, m;
int s[max_n];
int p[max_m];
int h[max_k];

int net[max_n];
inline void getnext(int p[],int lp) {
    int i = 0;int j = -1;
    net[0] = -1;
    while (i < lp) {
        if (j == -1 || p[i] <= j ? p[i] == p[j] : p[j] == 0)
            net[++i] = ++j;
        else j = net[j];
    }
}
inline int kmp(int s[],int ls,int p[],int lp) {
    int res = 0;
    int i = 0;int j = 0;
    while (i < ls) {
        if (j == -1 || s[i] <= j ? s[i] == p[j] : p[j] == 0) {
            ++i;
            ++j;
        }
        else j = net[j];
        if (j == lp) {
            j = net[j];
            ++res;
        }
    }return res;
}
int main() {
    n = read();k = read();
    for (register int i = 0;i < n;++i)s[i] = read();
    m = read();
    for (register int i = 0;i < m;++i)p[i] = read();
    for (register int i = 0;i < k;++i)h[i] = -1;
    for (register int i = 0;i < n;++i) {
        if (h[s[i]] == -1) {
            h[s[i]] = i;
            s[i] = 0;
        }
        else {
            int tmp = s[i];
            s[i] = i - h[s[i]];
            h[tmp] = i;
        }
    }
    for (register int i = 0;i < k;++i)h[i] = -1;
    for (register int i = 0;i < m;++i) {
        if (h[p[i]] == -1) {
            h[p[i]] = i;
            p[i] = 0;
        }
        else {
            int tmp = p[i];
            p[i] = i - h[p[i]];
            h[tmp] = i;
        }
    }
    getnext(p, m);
    write(kmp(s, n, p, m));
}