1999/Contest/京都大会

Problem H : Co-occurence Search

問題概要

巨大な文字列の中から、与えられた複数の文字を全て含む最小の (連続) 部分文字列を求める。

解法

多くの解法が考えられる。

三廻部の解法

それなりに工夫。

キーとなる文字が現れる場所を、キーごとにキューに保存する。

全てのキューの先頭要素のみからなる集合の中で最小要素と最大要素を取り出せば、それはキーの全ての文字を含む部分文字列の先頭と末尾である。

最小要素を除いて同じキューの次の値を追加する、ということを繰り返しながら、最短となる長さを求める。 (三廻部; Mar 16, 2004)

参考

プログラム・プロムナード」 2002年5月号 「複数の文字を含む区間の検索

議論・その他


ファイルを添付する

filecooc.txt 746件 [詳細] filetadokoro_cooc.cpp 677件 [詳細] filenoda_cooc.cpp 666件 [詳細] fileterashima_cooc.cpp 684件 [詳細] filehirano_WA_cooc.cpp 670件 [詳細] filecooc.out.txt 703件 [詳細] filemikurube_h.cpp 686件 [詳細]
[添付ファイル一覧] [全ページの添付ファイル一覧]
アップロード可能最大ファイルサイズは 10,240KB です。

管理者パスワード:

添付ファイル: filecooc.txt 746件 [詳細] filetadokoro_cooc.cpp 677件 [詳細] filenoda_cooc.cpp 666件 [詳細] fileterashima_cooc.cpp 684件 [詳細] filehirano_WA_cooc.cpp 670件 [詳細] filecooc.out.txt 703件 [詳細] filemikurube_h.cpp 686件 [詳細]

Last-modified: 2009-11-06 (金) 13:27:11 (3153d)