Rustコトハジメ

プログラミング言語Rustと競プロに関する情報をお届けします。

【ABC141-E Who Says a Pun?】Zアルゴリズムのverify

コンテスト中に解けなかったので勉強ライブ中に解いておきました。

問題

E - Who Says a Pun?

文字列中のオーバーラップしない2つの等しい部分文字列のうち、もっとも長いものの長さを求めよ

制約: N=103

方針

Nが小さいので二乗までは許される。

文字列の先頭をずらしつつZアルゴリズムを適用して、最大値を更新する。

実装

fn solve() {
    input!{
        N:usize,
        S:chars,
    }
    let mut s=vec![];
    for c in S {
        let n = c as u8 - 'Z' as u8;
        s.push(n as usize);
    }
    let mut maxv=0;
    for offset in 0..s.len()-1 {
        let z = z_algorithm(&s[offset..]);
        for i in 1..z.len() {
            // i番目を先頭とする文字列がs[offset..]と最長でどのくらいのprefixを持つか
            let len = z[i];
            if i >= len {
                maxv=max(maxv, len);
            }
        }
    }
    println!("{}",maxv);
}

考察

これを落としてしまったのは痛すぎる。

結論として、ロリハは二度と信用しない。

過去にも文字列系問題が出たが、やはり想定はZアルゴリズムだった。ロリハはハッシュ衝突を仕掛けられることがあるし、そもそも遅い。常にZアルゴリズムから考える。

F - Strings of Eternity