078 C K-th Substring¶

• created: 2022-12-13 tue
• ご意見・ご要望はissue・プルリク用のGitHubまで
• 競技プログラミングのためのF#入門
• GitHub上の対応ディレクトリ
• 公式ページ
• 公式解説

解説¶

公式解説の方針そのままの実装を考えます. 条件をみたす部分文字列をどう作るかがポイントで, 今回の条件ではとにかく手当たり次第に作ると諦めるのが肝心です.

文字列の各i番目からi+K-1番目までの部分文字列を作り倒すには, 例えば次のように書けばよいでしょう.

1
2
3
4
5

  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があるため, 素直にこれを使えばいいでしょう.

1
2
3
4
5

  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番目を取れば終わりです.