Problem H : Co-occurence Search †問題概要 †巨大な文字列の中から、与えられた複数の文字を全て含む最小の (連続) 部分文字列を求める。 解法 †多くの解法が考えられる。 三廻部の解法 †それなりに工夫。 キーとなる文字が現れる場所を、キーごとにキューに保存する。 全てのキューの先頭要素のみからなる集合の中で最小要素と最大要素を取り出せば、それはキーの全ての文字を含む部分文字列の先頭と末尾である。 最小要素を除いて同じキューの次の値を追加する、ということを繰り返しながら、最短となる長さを求める。 (三廻部; Mar 16, 2004) 参考 †「プログラム・プロムナード」 2002年5月号 「複数の文字を含む区間の検索」 議論・その他 †ファイルを添付する †cooc.txt 1509件 [詳細] tadokoro_cooc.cpp 1280件 [詳細] noda_cooc.cpp 1710件 [詳細] terashima_cooc.cpp 1284件 [詳細] hirano_WA_cooc.cpp 1327件 [詳細] cooc.out.txt 1493件 [詳細] mikurube_h.cpp 1710件 [詳細] |