プログラミングのお題スレ Part22 (863ﾚｽ)
上下前次1-新
抽出解除 ﾚｽ栞
ﾘﾛｰﾄﾞ規制です｡10分ほどで解除するので､他のﾌﾞﾗｳｻﾞへ避難してください｡
510(21): デフォルトの名無しさん [] 01/30(木)21:27 ID:te1+SH0T(1)
お題
ソース文字列と検索文字列が入力されます
検索文字列の文字をすべて含むソース文字列の部分文字列のうち
一番短い部分文字列を出力してください
DHBICEJAFG EIC → ICE
FDGJHCBIEA EIC → CBIE
FBHDCIJGEA EIC → CIJGE
JDIBGHCEAF EIC → IBGHCE
JBCIAGDHEF EIC → CIAGDHE
EJFBCAGIHD EIC → EJFBCAGI
IADCGJFBEH EIC → IADCGJFBE
IDFHBJGAEC EIC → IDFHBJGAEC
513: デフォルトの名無しさん [sage] 01/31(金)00:36 ID:MBodgIXJ(1)
>>510 ruby
https://ideone.com/K7lxJe
519(1): デフォルトの名無しさん [sage] 01/31(金)22:17 ID:bHXxdIdo(1)
>>510 c
https://ideone.com/MZt32o
524(1): 519 [sage] 02/01(土)17:22 ID:/Ur4AoNp(1)
>>510 c
https://ideone.com/tdT1q2
・若干の高速化
部分文字列を一文字ずつズラして検証していたのを
n = strcspnで探してn文字スキップへ
529(1): デフォルトの名無しさん [] 02/03(月)21:15 ID:swo++26S(1)
>>510
R
https://ideone.com/0Hr1lU
C++ (>>524と同じ巨大文字列での繰り返しあり)
https://ideone.com/7fJXjB
530(1): デフォルトの名無しさん [sage] 02/03(月)22:57 ID:VF4m0iMh(1)
>>510 c
https://ideone.com/L4xIAy
・f_529 は529さんのパクり
・f_strcspn_chr は strchr してから strcspn すると単純ながら若干の速度向上
531(1): 530 [sage] 02/04(火)21:13 ID:k8XtEdoq(1)
>>510 c
https://ideone.com/Mar3S7
・f_529direct は出現位置集めるのやめた
*min = strchr(*min + 1, **min)) でそのまま次へ
532(1): 531 [sage] 02/05(水)20:39 ID:mFRiRIqM(1/2)
>>510 c
https://ideone.com/jeAf1a
・デバッグと若干の整理
533: 532 [sage] 02/05(水)23:28 ID:mFRiRIqM(2/2)
>>510 java
https://ideone.com/EdHfzN
534(1): デフォルトの名無しさん [] 02/06(木)22:16 ID:u6r6iDwj(1)
>>510
C++
https://ideone.com/ywT3qw
>>529からの変更点
・sへのtの文字の出現位置を高速取得（1バイト文字のみに対応）
・sにtの同一文字が3回以上連続して出現する場合に最初と最後以外の位置を省略
537(3): 9 [sage] 02/07(金)21:20 ID:dMuAEB5V(1/4)
>510 Perl5
https://ideone.com/lceN9R
538(2): デフォルトの名無しさん [sage] 02/07(金)22:53 ID:ovhX7KXo(1/2)
>>510 c
https://ideone.com/uYlPLX
・f_537 は537さんのパクリ
544(2): 9 [sage] 02/08(土)00:22 ID:vma3KbbM(1/2)
>>510 Perl5、>>537 の修正版
https://ideone.com/klqLux
修正点
・>>537では間違って一番長い範囲を検出していたが、一番短い範囲に修正した。（サンプルデータではそれらの解はたまたま一致）
・パターンが3文字であることに依存する定数「2(=3 -1 )」をハードコードしている箇所があったので、パターン文字数次第で処理するように修正
・検出した候補文字列リストのうち一番短い物の検索のためにわざわざ候補リスト全体をsortするのをやめて
reduceによって長さが一番短い文字列を検索するように修正
List::Utils は言語処理系にデフォルトで付属のコアモジュール、
List::MoreUtils はCPANのオプションノジュールだがideoneのperlにはｲﾝｽｺされていたので使っちゃいましたﾃﾍﾍﾟﾛ
なお、候補文字列リストを作らず、ループの最内ifの中で一番短い文字列だけを記録していく様に記述すれば
大規模問題で若干効率が良くなるだろうけど、
まあいいや、もういいや。
546: デフォルトの名無しさん [] 02/08(土)08:27 ID:7bAG/IVE(1)
>>510
Wolfram Language
s = "DHBICEJAFG"
>> Out[1]= DHBICEJAFG
pattern = "EIC"
>> Out[2]= EIC
shortestMatch = \
(* 全通りの部分文字列を生成する *) \
ReplaceList[ Characters[ s ], {___, x__, ___} -> {x} ] \
(* 短い順、先頭に近い順に並べる *) \
// Sort \
(* 検索文字列の文字を全て含むものを選ぶ *) \
// Select[ ContainAll[ Characters[ pattern ] ] ] \
(* 1つ目を文字列として返す *) \
// Extract[ 1 ] // StringJoin
>> Out[3]= ICE
547: 9 [sage] 02/08(土)17:50 ID:HpUe4TZQ(1)
>>510 Perl5、>>544 をもう一回だけ改良
https://ideone.com/YkuK1w
改良点：
・検出された範囲の候補を一通りリストに蓄えて、あとでその中から最短のものを探す方式を止めて、
範囲を検索するループ内のifでその時点までの最短な範囲の判定と記録を行うようにした。
・CPANモジュールList::MoreUtilsのminmaxを使わない。
・コアモジュールList::Utilはminだけ使う。reduceは使わない。
なんだかPerlのコードらしい感じが減って、ベタな感じのコードになってしまいました
548(2): デフォルトの名無しさん [] 02/08(土)19:59 ID:EDI8nVtP(1/2)
>>510
C++
https://ideone.com/7EHx0H
>>534からの変更点
・minmax_elementを呼び出さずに済むようにして高速化
549(1): デフォルトの名無しさん [] 02/08(土)20:02 ID:EDI8nVtP(2/2)
>>510
C++
https://ideone.com/TluWQi
>>548では検索文字列が短くて高速化されたか分かりにくかったので、長くして529, 534, 548の
実行時間を比較してみると、効果が顕著に現れた。
552: デフォルトの名無しさん [sage] 02/09(日)12:47 ID:uN83pfj6(1)
>>510 c
https://ideone.com/D2AZMK
・両端に着目し、両端のみを更新しつつ調べていく（が、これといってパっとせず）
・f_both_ends はあくまで元の文字列s上を調べていく
・f_both_ends_v2 は「次」「隣」にアクセスしやすくした構造の上を調べていく
・あと実行時間の値ははげしくブレブレなので参考程度にとどめておいてね
554: デフォルトの名無しさん [] 02/09(日)21:31 ID:do9MXosP(2/3)
>>510
C++
https://ideone.com/bwvs06
>>548からの変更点
・データ構造を単純化したら速くなった
555: デフォルトの名無しさん [] 02/09(日)21:35 ID:do9MXosP(3/3)
>>510
https://ideone.com/46Tb28
>>549の実行速度比較に554を追加。548は不要な2行を削除した。検索文字列が短いのと長いのの両方をテスト。
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.045s