AtCoder 329. E - Stamp (搜索 + 思维

import java.util.Scanner;

class Main {
    static int n, m;
    static String s, t;
    static StringBuilder ox;

    /**
     * 思路 :
     *      思路的大门 : 题目要要求把x变成s, 我们可以反过来, 把s变成只有#的x, 所以我们就有了思路
     *           1. 从前往后遍历, 如果s的某一段和t相同, 那么我们就删除, 并且删除后变成连续的#了, 我们把#看成和任何字符都相同 (这里豁然开郎
     *                  比如 : AB# == ABC
     *           2. 如果s的一个位置删除了, 那么这个删除后的位置如果能产生下一个删除位置的话, 那么一定在当前删除位置左右的m个长度内 (可以自己动手画画图
     *           3. 我们避免一个位置重复搜索, 特判 ### != ABC
     *
     *           就这样用搜索删就好了, 注意边界以及下标问题
     * */

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        n = sc.nextInt(); m = sc.nextInt();
        s = sc.next(); t = sc.next();
        ox = new StringBuilder(s);

        for (int i = 0; i <= n - m; i ++ ) // 枚举每一个位置看是否可以删除
            if (check(i)) dfs(i);

//        System.out.println("ox -> " + ox);
//        System.out.println("s -> " + s);

        for (int i = 0; i < n; i ++ ) { // 看删除后的s是否全是#
            if (ox.charAt(i) != '#') {
                System.out.println("No");
                return ;
            }
        }

        System.out.println("Yes");
    }

    private static void f(int x) { // 删除操作
        for (int i = x; i <= x + m - 1; i ++ )
            ox.setCharAt(i, '#');
    }

    private static boolean check(int x) { // 检查 (不过多描述, 自己看)
        boolean f = false; // f的作用, 处理特判 ### != ABC 
        for (int i = 0; i < m; i ++ ) {
            if (ox.charAt(x + i) == '#') continue;
            if (ox.charAt(x + i) != t.charAt(i)) return false;
            f = true;
        }

        return f;
    }

    private static void dfs(int x) { // 搜索
        f(x); // 删除

        for (int i = Math.max(0, x - m); i < x; i ++ ) // 前m个位置
            if (check(i)) dfs(i);

        for (int i = x + 1; i <= x + m && i + m - 1 < n; i ++ ) // 后m个位置
            if (check(i)) dfs(i);
    }
}