1999/Contest/京都大会

Problem H : Co-occurence Search †

問題概要 †

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

解法 †

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

三廻部の解法 †

それなりに工夫。

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

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

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

参考 †

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

議論・その他 †

---

ファイルを添付する †

cooc.txt 1769件 [詳細] tadokoro_cooc.cpp 1458件 [詳細] noda_cooc.cpp 1824件 [詳細] terashima_cooc.cpp 1467件 [詳細] hirano_WA_cooc.cpp 1500件 [詳細] cooc.out.txt 1702件 [詳細] mikurube_h.cpp 1840件 [詳細]

[添付ファイル一覧] [全ページの添付ファイル一覧]
アップロード可能最大ファイルサイズは 10,240KB です。
添付ファイル:
管理者パスワード: Rename the filename to: