AtCoder Beginner Contest 329 E

https://atcoder.jp/contests/abc329/tasks/abc329_e

置き換える順序が大事なのですが、左から順に1文字ずつ合う状態を選んでいくとき、最近M個までの順序だけを覚えておけばよく、さらに上に最新の操作の下に埋もれてしまう操作は意味を成さないので、そこは無視すればよいです。そうすると合致する状態数が減ります。
下のコードはギリギリ通りました。Vecをビット演算を使ってusizeにすれば速くなるはずですが。

// Stamp
#![allow(non_snake_case)]

use std::collections::HashSet;


//////////////////// library ////////////////////

fn read<T: std::str::FromStr>() -> T {
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).ok();
    line.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>().split_whitespace()
            .map(|e| e.parse().ok().unwrap()).collect()
}

fn YesNo(b: bool) -> String {
    return (if b { "Yes" } else { "No" }).to_string()
}


//////////////////// process ////////////////////

fn read_input() -> (String, String) {
    let _v = read_vec::<usize>();
    let S: String = read();
    let T: String = read();
    (S, T)
}

type State = usize;

fn front_char(v: &Vec<usize>, T: &String) -> char {
    if v.is_empty() {
        '#'
    }
    else {
        let i = v[v.len()-1];
        T.as_bytes()[i] as char
    }
}

fn encode(v: &Vec<usize>) -> State {
    let mut n: State = v.len();
    for i in 0..v.len() {
        n += v[i] << (i*3+3)
    }
    n
}

fn decode(state: State) -> Vec<usize> {
    let L = state & 7;
    let mut v: Vec<usize> = vec![0; L];
    for i in 0..L {
        v[i] = (state >> (i*3+3)) & 7
    }
    v
}

fn next_states(state: State, c: char, T: &String) -> Vec<State> {
    let M = T.len();
    let v0 = decode(state);
    let v1: Vec<usize> = v0.iter().filter(|&&i| i < M-1).
                                            map(|i| i+1).collect();
    
    let mut states: Vec<State> = vec![];
    if T.as_bytes()[0] as char == c {
        states.push(1)
    }
    if front_char(&v1, T) == c {
        let state1 = encode(&v1);
        states.push(state1);
    for j in 0..(state1&7)+1 {
            let mut v2: Vec<usize> = vec![0];
            v2.extend(v1[j..].to_vec());
            if front_char(&v2, T) == c {
                let state2 = encode(&v2);
                states.push(state2)
            }
        }
    }
    states
}

fn to_string(state: State, T: &String) -> String {
    let v = decode(state);
    if v.is_empty() {
        return String::from("")
    }
    
    let M = T.len();
    let mut cs: Vec<char> = vec!['#'; M];
    for &j in v.iter() {
        for k in j..M {
            cs[k-j] = T.as_bytes()[k] as char
        }
    }
    cs.into_iter().collect::<String>()
}

fn F(S: String, T: String) -> bool {
    let N = S.len();
    let M = T.len();
    let mut states: Vec<State> = vec![0];
    for (_, c) in (0..N-M+1).zip(S.chars()) {
        let mut new_states: Vec<State> = vec![];
        for state in states.into_iter() {
            let ss = next_states(state, c, &T);
            new_states.extend(ss)
        }
        if new_states.is_empty() {
            return false
        }
        states = new_states.into_iter().
                    collect::<HashSet<State>>().
                    into_iter().collect()
    }
    
    let tail = S[N-M..].to_string();
    for state in states.into_iter() {
        let s = to_string(state, &T);
        if s == tail {
            return true
        }
    }
    false
}

fn main() {
    let (N, A) = read_input();
    println!("{}", YesNo(F(N, A)))
}