No-Subsequence Substring の解説

[l, r)で、含まない部分列が作れた時には、lを固定したとき、ありうるrはr - l個あるので

この前提をもってlを固定してrをできる限り大きくすることを考えます。

Tが小さいのでTに関しては各lの過程で都度考えることができるため、以下のことを操作します。

• はじめright = l - 1として処理を開始する
• 文字Tiがright + 1より先ではじめてはじめてTiが出てくるindexをnextとする
  • そのindexが見つからなかった場合はindex = nとして操作を終了する
• right = nextとする

として繰り返したときが伸ばせる最大のrとして得られます。

よってlを固定した時の部分問題が解けたので各lに対してこの問題をとくことで元の問題に回答できます。

fn main() {
    input! {
        s: Chars,
        t: Chars
    }
    let n = s.len();
    let alpha = ('a'..='z').collect_vec();
    let mut map = vec![BTreeSet::new(); alpha.len()];
    for i in 0..n {
        let idx = alpha.iter().position(|&e| e == s[i]).unwrap();
        map[idx].insert(i);
    }

    let mut ans = 0;
    for left in 0..s.len() {
        let mut right = left;
        for (i, &c) in t.iter().enumerate() {
            let idx = alpha.iter().position(|&e| e == c).unwrap();
            let search = if i == 0 {right} else {right + 1};
            let next = map[idx].range(search..).next();
            if let Some(&v) = next {
                right = v;
            } else {
                right = n;
                break;
            }
        }
        ans += right - left;
    }
    println!("{}", ans);
}