题目源于字节跳动2021秋招研发第二场第二题。

题意是说，给长度为n<10^5的字符串，里面包含十六进制数字（0~F），要求让这个字符串不能包含‘0010’这个子串，问最少要删除多少次。

其实这个子串很特殊，对于任意一个字符串，我总能找到一种方法使得我删除一个字符之后0010的个数减少一个。那么就是求一下出现了多少次0010即可。

但是如果给你的串不是0010而是一个随机的串呢？

又到了经典的“不包含子串”时间了。这种题一般是在KMP上dp。

先对模式串做一次KMP。

枚举原串的每一位，再枚举KMP的每个状态，若做匹配的时候没有匹配到结尾，说明不含模式串，此时可以直接对状态取最小，如果匹配到最后了则不能进行转移，因为此时表示含子串。

在原串i匹配到模式串j的情况下，如果我删除这一位，那么原串i+1则匹配模式串j，同时删除次数加一。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
mt19937 mrand(random_device{}());
int rnd(int x) { return mrand() % x;}
int ne[10], f[100005][10];
char str[100005];
char p[10] = " 0010";
int T;
int main()
{
    // time_t startt = clock();
    int m = 4;
    for(int i = 2, j = 0; i <= m; i++)
    {
        while(j && p[i] != p[j + 1]) j = ne[j];
        if(p[i] == p[j + 1]) j++;
        ne[i] = j;
    }
    scanf("%d", &T);
    while(T--)
    {
        scanf("%s", str + 1);
        int n = strlen(str + 1);

        for(int i = 0; i <= n; i++)
            for(int j = 0; j <= 4; j++) f[i][j] = 0x3f3f3f;
        f[0][0] = 0;
        for(int i = 0; i < n; i++)
        {
            for(int j = 0; j < m; j++)
            {
                int u = j;
                while(u && str[i + 1] != p[u + 1]) u = ne[u];
                if(str[i + 1] == p[u + 1]) u++;
                if(u < m) f[i + 1][u] = min(f[i + 1][u], f[i][j]);
                f[i + 1][j] = min(f[i + 1][j], f[i][j] + 1);
            }
        }
        int res = 0x3f3f3f;
        for(int i = 0; i < m; i++) res = min(res, f[n][i]);
        cout << res << endl;
    }
    // cerr << "~ #" << " done! time : " << (double)(clock()-startt) << " ms" << endl;
    // cerr << "~ #" << " done! time : " << (double)(clock()-startt)/CLOCKS_PER_SEC << " s" << endl;
}

• 因为没有地方交题，所以不保证代码本身正确。