在没有库函数的情况下查找字符串是否是 Sml 中另一个字符串的子字符串

Question

我正在尝试编写一个 subString : string * string -> int 的函数检查第一个字符串是否是第二个字符串的子字符串并且区分大小写。

如果第一个字符串是子字符串，我想 return 索引从 0 开始，如果不是，则从 -1 开始。如果它出现多次只是 return 第一次出现的索引。

例如：

subString("bc","abcabc") ===>1
subString("aaa","aaaa") ===>0
subString("bc","ABC") ===>-1

我在思考这个问题时遇到了很多麻烦，因为我不太熟悉 sml 或在 sml 中使用字符串，而且我不应该使用任何内置函数，如 String.sub.

不过我可以使用辅助函数。

我能想到的就是在辅助函数中以某种方式使用 explode 并以某种方式检查列表然后将它们内爆，但是我如何获得索引位置？

我只有

fun subString(s1,s2) =
     if null s2 then ~1
     else if s1 = s2 then 0
     else 1+subString(s1, tl s2);

我正在考虑使用一个辅助函数来分解字符串，然后比较两者，但我不知道如何让它工作。

Answer 1

这已经是一个很好的开始了，但是还有一些小问题：

在您的递归情况下，您将递归结果加 1，即使递归应用程序未找到子字符串并返回 -1。您应该在加 1 之前检查结果是否为 -1。

在第二行检查两个字符串是否相等。如果你这样做，你只会找到一个以该子字符串结尾的子字符串。所以你真正想在第 2 行中做的是测试 s2 是否以 s1 开头。我建议您编写一个执行该测试的辅助函数。对于这个辅助函数，您确实可以使用 explode，然后递归地检查列表的第一个字符是否相同。一旦你有了这个辅助函数，就在第 2 行使用它而不是等式测试。

Answer 2

I am not supposed to use any built in functions like String.sub

可惜了！由于字符串具有抽象接口，而列表可以直接访问其主要构造函数 [] 和 ::，因此您必须使用库函数来获取 anywhere 带字符串。 explode 也是一个库函数。但是好吧，如果你的约束是你必须将你的字符串转换成一个列表来解决这个练习，那就这样吧。

鉴于您当前的代码，

fun subString(s1,s2) =
     if null s2 then ~1
     else if s1 = s2 then 0
     else 1+subString(s1, tl s2);

我在这里感觉到一个问题：

   subString ([#"b",#"c"], [#"a",#"b",#"c",#"d"])
~> if null ([#"a",#"b",#"c",#"d"]) then ... else
   if [#"b",#"c"] = [#"a",#"b",#"c",#"d"] then ... else
   1 + subString([#"b",#"c"], [#"b",#"c",#"d"])

~> 1 + subString([#"b",#"c"], [#"b",#"c",#"d"])
~> 1 + if null ([#"b",#"c",#"d"]) then ... else
       if [#"b",#"c"] = [#"b",#"c",#"d"] then ... else
       1 + subString([#"b",#"c"], [#"c",#"d"])

似乎检查 s1 = s2 还不够：我们应该喜欢说 [#"b",#"c"] 是 [#"b",#"c",#"d"] 的子串，因为它是 [#"b",#"c",#"d"] 的前缀，而不是因为它是等价的。使用 s1 = s2 你最终会检查某些东西是有效的后缀，而不是有效的 子字符串 。所以你需要把s1 = s2改成更聪明的东西。

也许您可以构建一个辅助函数来确定一个列表是否是另一个列表的前缀并在此处使用它？

至于通过 explode 将您的字符串放入列表来解决此练习：这是非常低效的，以至于标准 ML 的姊妹语言 Ocaml 从库中 explode entirely removed：

The functions explode and implode were in older versions of Caml, but we omitted them from OCaml because they encourage inefficient code. It is generally a bad idea to treat a string as a list of characters, and seeing it as an array of characters is a much better fit to the actual implementation.

首先，String.isSubstring already exists，这是一个已解决的问题。但如果不是，并且有人想组合地写这个，并且 String.sub 不是作弊（它正在访问字符串中的字符，类似于通过 [=30 匹配列表的头部和尾部的模式=])，那么让我鼓励您编写高效、可组合且功能强大的代码：

(* Check that a predicate holds for all (c, i) of s, where
 * s is a string, c is every character in that string, and
 * i is the position of c in s. *)
fun alli s p =
    let val stop = String.size s
        fun go i = i = stop orelse p (String.sub (s, i), i) andalso go (i + 1)
    in go 0 end

(* needle is a prefix of haystack from the start'th index *)
fun isPrefixFrom (needle, haystack, start) =
    String.size needle + start <= String.size haystack andalso
    alli needle (fn (c, i) => String.sub (haystack, i + start) = c)

(* needle is a prefix of haystack if it is from the 0th index *)
fun isPrefix (needle, haystack) =
    isPrefixFrom (needle, haystack, 0)

(* needle is a substring of haystack if is a prefix from any index *)
fun isSubstring (needle, haystack) =
    let fun go i =
            String.size needle + i <= String.size haystack andalso
            (isPrefixFrom (needle, haystack, i) orelse go (i + 1))
    in go 0 end

在构建使用列表递归而不是字符串索引递归的 isSubstring 时，您可以重复使用这里的总体思路，即抽象地构建算法：needle 是haystack 可以更简单地定义为 needle 是 haystack 的前缀，从 haystack 中的任何有效位置开始计数（当然不会超过 haystack ).确定某物是否是前缀容易得多，使用列表递归更容易！

这个建议会给你留下一个模板，

fun isPrefix ([], _) = ...
  | isPrefix (_, []) = ...
  | isPrefix (x::xs, y::ys) = ...

fun isSubstring ([], _) = ...
  | isSubstring (xs, ys) = ... isPrefix ... orelse ...

至于优化字符串索引递归解决方案，您可以通过使 isPrefixFrom 成为只能由 isPrefix 和 isSubstring；否则不安全。

测试这个，

- isSubstring ("bc", "bc");
> val it = true : bool
- isSubstring ("bc", "bcd");
> val it = true : bool
- isSubstring ("bc", "abc");
> val it = true : bool
- isSubstring ("bc", "abcd");
> val it = true : bool
- isSubstring ("bc", "");
> val it = false : bool

在没有库函数的情况下查找字符串是否是 Sml 中另一个字符串的子字符串

Finding if a string is a substring of another in Sml without library functions

string

recursion

substring

sml

ml