Range Search Query の解説

部分文字列を連続でなくても良いと思ってWAを重ねた。

連続部分文字列ならばTを部分文字列として持つT[0]のindexを持っておいて、

(l, r)のクエリの時には一番lにちかいindexを検索すればOK (そうじゃなくちゃ無駄なので)

この時に検索されたindexが iだとすると、i + t.len() - 1 <= rであればYes

fn main() {
    input! {
        q: usize,
        s: Chars,
        t: Chars,
        lr: [(Usize1, Usize1); q]
    }
    let mut set = BTreeSet::new();
    for i in 0..s.len() {
        if i + t.len() - 1 >= s.len() {
            continue;
        }
        let mut tt = vec![];
        for j in 0..t.len() {
            tt.push(s[i + j]);
        }
        if tt == t {
            set.insert(i);
        }
    }
    let ans = lr
        .iter()
        .map(|&(l, r)| {
            let &next = set.range(l..).next().unwrap_or(&(usize::MAX / 2));
            let goal = next + t.len() - 1;
            if goal <= r {
                "Yes"
            } else {
                "No"
            }
        })
        .join("\n");
    println!("{}", ans);
}