ABC211 C - chokudai

[tipstar0125]

https://atcoder.jp/contests/abc211/tasks/abc211_c https://atcoder.jp/contests/abc211/submissions/47585101

[tipstar0125]

input! {
    S: Chars
}

let T = "chokudai".chars().collect_vec();
let mut dp = vec![vec![Mod::zero(); T.len() + 1]; S.len() + 1];
for i in 0..=S.len() {
    dp[i][0] = Mod::one();
}

for i in 1..=S.len() {
    let s = S[i - 1];
    for j in 1..=T.len() {
        let t = T[j - 1];
        dp[i][j] = dp[i - 1][j];
        if s == t {
            let z = dp[i - 1][j - 1];
            dp[i][j] += z;
        }
    }
}
println!("{}", dp[S.len()][T.len()].value());

[tipstar0125]

• Sを前から順番に見ていき、Tのいずれかと一致したら、既に数えた数に加えて、一つ前の文字列の数を加える（つまり、既に数えられた一つ前の文字ぶんだけ、今いる時点までの文字列のパターンが増える）

[tipstar0125]

類題

• Moja お茶コン2 ABAB: https://mojacoder.app/users/shinnshinn/problems/abab-str
  • Ans: https://mojacoder.app/users/shinnshinn/problems/abab-str/submissions/080d4793-bc9d-4dc6-ac10-636fc7ef3855