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);
}
}
AtCoder 329. E - Stamp (搜索 + 思维
发布时间 2023-11-26 14:54:31作者: 李菜菜想获奖