search

yosupo06 / library-checker-problems

The problem data (Test case generator, judge's solution, task, ...) of Library Checker
https://judge.yosupo.jp/
Apache License 2.0
509 stars 117 forks source link

[問題案] KMP #857

Open SSRS-cp opened 2 years ago

SSRS-cp commented 2 years ago

複数の出題形式が考えられそうです

・文字列が与えられるので、各 prefix について prefix と suffix が一致する最大文字数を求める。 ・文字列を動的に管理する。「後ろに文字を追加」「最後の文字を削除」「ある prefix が指定されるので、prefix と suffix が一致する最大文字数を答える」のクエリを処理

yosupo06 commented 1 year ago

KMPは実はMPだ　みたいな話をよく聞くんですが、実はわたしはあまり分かってません　要調査かも

おそらく1個目のやつはとても有名なやつで、2個目は競プロでよく見るやつなので、両方あっていいかもです

SSRS-cp commented 1 year ago

1 個目のやつは MP でもできて、2 個目のやつは KMP が必要 (MP だと計算量が愚直と同じオーダーになる場合が存在する) という認識をしています

SSRS-cp commented 1 year ago

https://snuke.hatenablog.com/entry/2017/07/18/101026

yosupo06 commented 1 year ago

求めたいもの(ver 1): 各iについて「S[0..i]の部分文字列のうち、prefixでもsuffixでもあるもののうち最長の長さ」

で、これを求めるアルゴリズムがKMPとかMPとかっぽさそうです

↑のテーブル自体の名前は、KMP Tableとかborderとか名前がついていそう？