Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/542-6bf2382c
この記事にトラックバックする(FC2ブログユーザー)

Aizu 1215 - Co-occurrence Search (この記事を編集する[管理者用])

Source

ACM/ICPC Kyoto, Japan 1999
ZJU 1672
Aizu 1215

問題概要

長さnの文字列とk文字の異なる文字が与えられる.
部分文字列でk文字全てを含むような物の中で長さ最小のものを探す問題.
その中で一番最初に出てくるものと,長さ最小の部分文字列が何個あるか(異なるものも2回出現したら2回カウント)を出力する.
nは1000000以下でkは50以下.
入力,出力の形式は,全て1行に72文字までで改行すること.

解法

尺取りメソッド.O(n+k)で計算できる.

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/542-6bf2382c
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。