競技プログラミングのためのF#入門
GitHub上の対応ディレクトリ 公式ページ 公式解説 解説
公式解説の方針そのままの実装を考えます. 条件をみたす部分文字列をどう作るかがポイントで, 今回の条件ではとにかく手当たり次第に作ると諦めるのが肝心です.
文字列の各i
番目からi+K-1
番目までの部分文字列を作り倒すには, 例えば次のように書けばよいでしょう.
| let S,K = "aba",4
let n = S.Length - 1
[|0..n|] |> Array.map (fun i -> [|i..(min n (i+K-1))|] |> Array.map (fun j -> S.[i..j]))
// val it: string[][] = [|[|"a"; "ab"; "aba"|]; [|"b"; "ba"|]; [|"a"|]|]
|
この返り値はもちろん文字列の配列の配列で, 型はstring[][]
です. これをフラットにする, つまりstring[]
にするにはArray.concat
を作用させればよいです. しかし標準でArray.map
の結果をArray.concat
してくれる関数Array.collect
があるため, 素直にこれを使えばいいでしょう.
| let S,K = "aba",4
let n = S.Length - 1
[|0..n|] |> Array.collect (fun i -> [|i..(min n (i+K-1))|] |> Array.map (fun j -> S.[i..j]))
// val it: string[] = [|"a"; "ab"; "aba"; "b"; "ba"; "a"|]
|
上の出力を見るとわかるように"a"
が二つ出てきます. あとはこの重複をArray.distinct
で潰し, Array.sort
してK
番目を取れば終わりです.
Previous: 077 A - 01 Matrix Next: 079 D Handstand back to top