[過去ﾛｸﾞ] プログラミングのお題スレ Part17 (1002ﾚｽ)
上下前次1-新
抽出解除 ﾚｽ栞

---

このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索 歴削→次ｽﾚ 栞削→次ｽﾚ 過去ﾛｸﾞﾒﾆｭｰ

---

466(6): 2020/05/09(土)20:03 ID:slqshlLL(1) AAS
お題
文字列Sが与えらえる。Sの部分列に"odai"は何個あるか？

[1] odadai => 3
部分列は以下の3通り
oda__i
od__ai
o__dai

[2] odaiodai => 5

[3] ooooddddaaaaiiii => 256

[4] daioadiao => 0

---

467: 2020/05/09(土)20:12 ID:I3214lBo(1) AAS
>>466
greedy algorithmしか思い浮かばんがいい方法があるのかね

---

469: 2020/05/09(土)21:12 ID:CDHXGmMd(1) AAS
>>466
D 再帰の力ってすげー
size_t count_substring(string target, string from) {
if (target.length == 0) {
return 1;
} else if (from.length == 0) {
return 0;
} else if (target[0] == from[0]) {
return count_substring(target[1..$], from[1..$]) + count_substring(target, from[1..$]);
} else {
省3

---

470: 2020/05/09(土)22:25 ID:146lBXch(1) AAS
>>466
haskell
f [] _=1
f _ []=0
f (x:xs) (y:ys)
| x==y = f xs ys+(f (x:xs) ys)
| otherwise = f (x:xs) ys

f "odai" "odadai" -> 3

---

472: 2020/05/10(日)08:58 ID:4OJfHckY(1) AAS
>>466 Ruby
外部ﾘﾝｸ:ideone.com
文字列処理を減らしたいので 2pass化
"odadai" => [[0], [1, 3], [2, 4], [5]] # 2passでは 左が小さな組み合わせをカウント
"odaiodai" => [[0, 4], [1, 5], [2, 6], [3, 7]]

---

473(3): 466 2020/05/10(日)13:59 ID:gIVDr8oL(1) AAS
入力サイズが小さいと簡単みたいなので、入力例を追加します。

[1]〜[4]の入力を1000回繰り返した文字列を入力とした場合

[1'] 167501334000
[2'] 668668500500
[3'] 10730784064000
[4'] 999666166500

---

486(1): 2020/05/12(火)19:39 ID:MKYG7Wu5(1) AAS
>>466 Ruby
def f(a,b)
r=0
v=b.chars
a.chars.combination(b.size){|x| r+=1 if x==v}
r
end

---

上下前次1-新書関写板覧索設栞歴

---

ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ

---

ぬこの手 ぬこTOP 0.173s*