Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

LiveArchive 4126 - Password Suspects (この記事を編集する[管理者用])

Source

ACM/ICPC World Finals - Banff Springs, Alberta - 2007/2008
LiveArchive 4126

問題概要

10文字以下のキーワードがm個与えられる.
長さnのアルファベット小文字から文字列で,キーワードを全部部分文字列として含むようなものの数を求める問題.
また,答えが42以下なら,全部列挙する.
nは25以下,mは10以下.答えは10^15以下であることが保証されている.

解法

DP.
現在何文字目か,既に含まれた文字列,最後はどの文字列に対して何文字目まで一致しているか,で状態数はだいたいO(n*2^m*m*10).
10はキーワードの文字列の長さ.
計算時間量は状態数×O(アルファベットの数=26)ぐらいで可能だけど,もうちょっと非効率的なのでも通る.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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