f# - 如何在 F# 中的字符串中查找子字符串？

Question

我在网上找到了一个 f# 的“有趣”项目，其背后的想法是找到给定字符串中的子字符串数。

这是提示:

Description:
You are given a DNA sequence:
a string that contains only characters 'A', 'C', 'G', and 'T'.
Your task is to calculate the number of substrings of sequence,
in which each of the symbols appears the same number of times.

Example 1:
For sequence = "ACGTACGT", the output should be 6
All substrings of length 4 contain each symbol exactly once (+5),
and the whole sequence contains each symbol twice (+1).

Example 2:
For sequence = "AAACCGGTTT", the output should be 1
Only substring "AACCGGTT" satisfies the criterion above: it contains each symbol twice.


Input: String, a sequence that consists only of symbols 'A', 'C', 'G', and 'T'.
Length constraint: 0 < sequence.length < 100000.

Output: Integer, the number of substrings where each symbol appears equally many times.

我不确定该去哪里，或者更具体地说，我不知道该怎么做。我在互联网上环顾四周，试图找到我应该做的事情，但我只找到了以下代码(我添加了输入变量 var 变量，并将显示“事物”更改为 输入 然后是要搜索的子字符串(我希望这是有道理的)):

open System

let countSubstring (where :string) (what : string) =
match what with
| "" -> 0
| _ -> (where.Length - where.Replace(what, @"").Length) / what.Length


[<EntryPoint>]
let main argv =

let input = System.Console.ReadLine();
let var = input.Length;
Console.WriteLine(var);
let show where what =
    printfn @"countSubstring(""%s"", ""%s"") = %d" where what (countSubstring where what)
show input "ACGT"
show input "CGTA"
show input "GTAC"
show input "TACG"
0

无论如何，如果有人能帮助我解决这个问题，我将不胜感激。

提前致谢

Answer 1

这是一个解决方案，它生成长度可被 4 整除的所有子串，然后计算其中有多少具有相同数量的符号。请注意，如果子串的长度不能被 4 整除，则它不能有相同数量的四个不同符号。

let hasEqualAmountOfSymbols (substring : string) =
    let symbolAppearances =
        ['A'; 'C'; 'G'; 'T']
        |> List.map (fun symbol ->
            substring
            |> Seq.filter ((=) symbol)
            |> Seq.length)
    symbolAppearances
    |> List.pairwise
    |> List.forall (fun (x, y) -> x = y)


let countSubstrings input =
    let potentialSubstrings =
        let lastIndex = String.length input - 1
        [ for i in 0 .. lastIndex do
            for j in i + 3 .. 4 .. lastIndex do
                yield input.Substring(i, j - i + 1) ]
    potentialSubstrings
    |> List.filter hasEqualAmountOfSymbols
    |> List.length


countSubstrings "ACGTACGT" // -> 6
countSubstrings "AAACCGGTTT" // -> 1