プログラミングのお題スレ Part22 (858ﾚｽ)
プログラミングのお題スレ Part22 http://mevius.5ch.net/test/read.cgi/tech/1691038333/
上
下
前次
1-
新
通常表示
512ﾊﾞｲﾄ分割
ﾚｽ栞
抽出解除
ﾚｽ栞
510: デフォルトの名無しさん [] 2025/01/30(木) 21:27:24.39 ID:te1+SH0T お題 ソース文字列と検索文字列が入力されます 検索文字列の文字をすべて含むソース文字列の部分文字列のうち 一番短い部分文字列を出力してください DHBICEJAFG EIC → ICE FDGJHCBIEA EIC → CBIE FBHDCIJGEA EIC → CIJGE JDIBGHCEAF EIC → IBGHCE JBCIAGDHEF EIC → CIAGDHE EJFBCAGIHD EIC → EJFBCAGI IADCGJFBEH EIC → IADCGJFBE IDFHBJGAEC EIC → IDFHBJGAEC http://mevius.5ch.net/test/read.cgi/tech/1691038333/510
513: デフォルトの名無しさん [sage] 2025/01/31(金) 00:36:51.89 ID:MBodgIXJ >>510 ruby https://ideone.com/K7lxJe http://mevius.5ch.net/test/read.cgi/tech/1691038333/513
519: デフォルトの名無しさん [sage] 2025/01/31(金) 22:17:10.46 ID:bHXxdIdo >>510 c https://ideone.com/MZt32o http://mevius.5ch.net/test/read.cgi/tech/1691038333/519
524: 519 [sage] 2025/02/01(土) 17:22:30.12 ID:/Ur4AoNp >>510 c https://ideone.com/tdT1q2 ・若干の高速化 部分文字列を一文字ずつズラして検証していたのを n = strcspnで探してn文字スキップへ http://mevius.5ch.net/test/read.cgi/tech/1691038333/524
529: デフォルトの名無しさん [] 2025/02/03(月) 21:15:02.53 ID:swo++26S >>510 R https://ideone.com/0Hr1lU C++ (>>524と同じ巨大文字列での繰り返しあり) https://ideone.com/7fJXjB http://mevius.5ch.net/test/read.cgi/tech/1691038333/529
530: デフォルトの名無しさん [sage] 2025/02/03(月) 22:57:52.37 ID:VF4m0iMh >>510 c https://ideone.com/L4xIAy ・f_529 は529さんのパクり ・f_strcspn_chr は strchr してから strcspn すると単純ながら若干の速度向上 http://mevius.5ch.net/test/read.cgi/tech/1691038333/530
531: 530 [sage] 2025/02/04(火) 21:13:55.63 ID:k8XtEdoq >>510 c https://ideone.com/Mar3S7 ・f_529direct は出現位置集めるのやめた *min = strchr(*min + 1, **min)) でそのまま次へ http://mevius.5ch.net/test/read.cgi/tech/1691038333/531
532: 531 [sage] 2025/02/05(水) 20:39:11.49 ID:mFRiRIqM >>510 c https://ideone.com/jeAf1a ・デバッグと若干の整理 http://mevius.5ch.net/test/read.cgi/tech/1691038333/532
533: 532 [sage] 2025/02/05(水) 23:28:39.35 ID:mFRiRIqM >>510 java https://ideone.com/EdHfzN http://mevius.5ch.net/test/read.cgi/tech/1691038333/533
534: デフォルトの名無しさん [] 2025/02/06(木) 22:16:32.16 ID:u6r6iDwj >>510 C++ https://ideone.com/ywT3qw >>529からの変更点 ・sへのtの文字の出現位置を高速取得（1バイト文字のみに対応） ・sにtの同一文字が3回以上連続して出現する場合に最初と最後以外の位置を省略 http://mevius.5ch.net/test/read.cgi/tech/1691038333/534
537: 9 [sage] 2025/02/07(金) 21:20:22.98 ID:dMuAEB5V >510 Perl5 https://ideone.com/lceN9R http://mevius.5ch.net/test/read.cgi/tech/1691038333/537
538: デフォルトの名無しさん [sage] 2025/02/07(金) 22:53:14.41 ID:ovhX7KXo >>510 c https://ideone.com/uYlPLX ・f_537 は537さんのパクリ http://mevius.5ch.net/test/read.cgi/tech/1691038333/538
544: 9 [sage] 2025/02/08(土) 00:22:55.52 ID:vma3KbbM >>510 Perl5、>>537 の修正版 https://ideone.com/klqLux 修正点 ・>>537では間違って一番長い範囲を検出していたが、一番短い範囲に修正した。（サンプルデータではそれらの解はたまたま一致） ・パターンが3文字であることに依存する定数「2(=3 -1 )」をハードコードしている箇所があったので、パターン文字数次第で処理するように修正 ・検出した候補文字列リストのうち一番短い物の検索のためにわざわざ候補リスト全体をsortするのをやめて reduceによって長さが一番短い文字列を検索するように修正 List::Utils は言語処理系にデフォルトで付属のコアモジュール、 List::MoreUtils はCPANのオプションノジュールだがideoneのperlにはｲﾝｽｺされていたので使っちゃいましたﾃﾍﾍﾟﾛ なお、候補文字列リストを作らず、ループの最内ifの中で一番短い文字列だけを記録していく様に記述すれば 大規模問題で若干効率が良くなるだろうけど、 まあいいや、もういいや。 http://mevius.5ch.net/test/read.cgi/tech/1691038333/544
546: デフォルトの名無しさん [] 2025/02/08(土) 08:27:20.39 ID:7bAG/IVE >>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 http://mevius.5ch.net/test/read.cgi/tech/1691038333/546
547: 9 [sage] 2025/02/08(土) 17:50:15.20 ID:HpUe4TZQ >>510 Perl5、>>544 をもう一回だけ改良 https://ideone.com/YkuK1w 改良点： ・検出された範囲の候補を一通りリストに蓄えて、あとでその中から最短のものを探す方式を止めて、 範囲を検索するループ内のifでその時点までの最短な範囲の判定と記録を行うようにした。 ・CPANモジュールList::MoreUtilsのminmaxを使わない。 ・コアモジュールList::Utilはminだけ使う。reduceは使わない。 なんだかPerlのコードらしい感じが減って、ベタな感じのコードになってしまいました http://mevius.5ch.net/test/read.cgi/tech/1691038333/547
548: デフォルトの名無しさん [] 2025/02/08(土) 19:59:09.70 ID:EDI8nVtP >>510 C++ https://ideone.com/7EHx0H >>534からの変更点 ・minmax_elementを呼び出さずに済むようにして高速化 http://mevius.5ch.net/test/read.cgi/tech/1691038333/548
549: デフォルトの名無しさん [] 2025/02/08(土) 20:02:06.41 ID:EDI8nVtP >>510 C++ https://ideone.com/TluWQi >>548では検索文字列が短くて高速化されたか分かりにくかったので、長くして529, 534, 548の 実行時間を比較してみると、効果が顕著に現れた。 http://mevius.5ch.net/test/read.cgi/tech/1691038333/549
552: デフォルトの名無しさん [sage] 2025/02/09(日) 12:47:59.38 ID:uN83pfj6 >>510 c https://ideone.com/D2AZMK ・両端に着目し、両端のみを更新しつつ調べていく（が、これといってパっとせず） ・f_both_ends はあくまで元の文字列s上を調べていく ・f_both_ends_v2 は「次」「隣」にアクセスしやすくした構造の上を調べていく ・あと実行時間の値ははげしくブレブレなので参考程度にとどめておいてね http://mevius.5ch.net/test/read.cgi/tech/1691038333/552
554: デフォルトの名無しさん [] 2025/02/09(日) 21:31:24.58 ID:do9MXosP >>510 C++ https://ideone.com/bwvs06 >>548からの変更点 ・データ構造を単純化したら速くなった http://mevius.5ch.net/test/read.cgi/tech/1691038333/554
555: デフォルトの名無しさん [] 2025/02/09(日) 21:35:08.87 ID:do9MXosP >>510 https://ideone.com/46Tb28 >>549の実行速度比較に554を追加。548は不要な2行を削除した。検索文字列が短いのと長いのの両方をテスト。 http://mevius.5ch.net/test/read.cgi/tech/1691038333/555
556: 警備員[Lv.19] [] 2025/02/10(月) 13:21:24.86 ID:g+w4FSG9 >>510 Kotlin 出来たことは出来たが、もっと簡単に出来そうな気がしてきた。 https://paiza.io/projects/RwNXYMH6q3P6v0vx9zbZng http://mevius.5ch.net/test/read.cgi/tech/1691038333/556
567: デフォルトの名無しさん [sage] 2025/02/11(火) 17:43:14.68 ID:7RexIvi8 >>510 lisp https://ideone.com/qm4PsV http://mevius.5ch.net/test/read.cgi/tech/1691038333/567
ﾒﾓ帳
(0/65535文字)
上
下
前次
1-
新
書
関
写
板
覧
索
設
栞
歴
ｽﾚ情報
赤ﾚｽ抽出
画像ﾚｽ抽出
歴の未読ｽﾚ
AAｻﾑﾈｲﾙ
Google検索
Wikipedia
ぬこの手
ぬこTOP
0.035s