Stamp の解説

逆から順に考える。

12 2
XYXXYXXYYYXY
XY

の例で考える。

完成形から考えると、最後に追加したところはかならずTが現れるので、それを剥がす。

XYをはがせる。剥がしたところは.にする。

..X..X..YY..

.になったところにはあとからXYが重ね塗りされるので何でも来て良い。 よって、制約がゆるくなった状態で、さっきと同じ問題を解く。

X. の箇所をXYと塗ればよいことがわかるので、これも剥がす。 また、.YもXYと塗れば良い。

.........Y.. -> ............

全部.にできたのでyes。逆にこれができないならno.

Mが最大5文字で優しいので何をやっても通る。

fn main() {
    input! {
        n: usize,
        m: usize,
        s: Chars,
        t: Chars
    }
    let mut que = VecDeque::new();
    let mut vis = vec![false; n];
    let mut ans = vec![false; n];
    'la: for i in 0..n {
        if i + m - 1 >= n {
            break;
        }
        for j in 0..m {
            if s[i + j] != t[j] {
                continue 'la;
            }
        }
        for j in 0..m {
            ans[i + j] = true;
        }
        vis[i] = true;
        que.push_back(i);
    }

    while !que.is_empty() {
        let v = que.pop_front().unwrap();
        for j in 0..m {
            for nan in 0..m {
                if v + j < nan {
                    continue;
                }
                let start = v + j - nan;
                if start + m - 1 >= n {
                    continue;
                }
                let mut flg = true;
                for (count, idx) in (start..=start + m - 1).enumerate() {
                    if ans[idx] {
                        continue;
                    }
                    if s[idx] != t[count] {
                        flg = false;
                        break;
                    }
                }
                if !flg {
                    continue;
                }
                for (count, idx) in (start..=start + m - 1).enumerate() {
                    if ans[idx] {
                        continue;
                    }
                    ans[idx] = true;
                }
                if vis[start] {
                    continue;
                }
                vis[start] = true;
                que.push_back(start);
            }
        }
    }
    let ans = ans.iter().all(|&e|e);
    let ans = if ans {"Yes"} else {"No"};
    println!("{}", ans);
}