Я пытаюсь написать функцию, которая subString : string * string -> int который проверяет, является ли первая строка подстрокой второй и учитывает регистр.
Я хочу вернуть индекс, начиная с 0, если первая строка является подстрокой или -1, если это не так. если он появляется несколько раз, просто верните индекс первого появления.
например:
subString("bc","abcabc") ===>1
subString("aaa","aaaa") ===>0
subString("bc","ABC") ===>-1
У меня много проблем с обдумыванием этого, потому что я не слишком хорошо знаком с sml или использую строки в sml, и я не должен использовать какие-либо встроенные функции, такие как String.sub.
Однако я могу использовать вспомогательные функции.
все, что я могу придумать, это как-то использовать взрыв во вспомогательной функции и как-то проверять списки, а затем взрывать их, но как мне получить проиндексированную позицию?
все, что у меня есть
fun subString(s1,s2) =
if null s2 then ~1
else if s1 = s2 then 0
else 1+subString(s1, tl s2);
Я думаю об использовании вспомогательной функции, которая взрывает строки, а затем, возможно, сравнивает их, но я не могу понять, как заставить это работать.
Это уже действительно хорошее начало, но есть небольшие проблемы:
В вашем рекурсивном случае вы добавляете 1 к рекурсивному результату, даже если рекурсивное приложение не нашло подстроку и вернуло -1. Вы должны проверить, равен ли результат -1, прежде чем добавлять 1.
Во второй строке вы проверяете, равны ли две строки. Если вы сделаете это, вы найдете подстроку только в том случае, если строка заканчивается этой подстрокой. Итак, что вы действительно хотите сделать в строке 2, так это проверить, начинается ли s2 с s1. Я бы порекомендовал вам написать вспомогательную функцию, которая выполняет этот тест. Для этой вспомогательной функции вы действительно можете использовать взорваться, а затем рекурсивно проверить, идентичны ли первые символы списков. Если у вас есть эта вспомогательная функция, используйте ее в строке 2 вместо проверки на равенство.
I am not supposed to use any built in functions like
String.sub
Как жаль! Поскольку строки имеют абстрактный интерфейс, в то время как вы со списками имеете прямой доступ к его первичным конструкторам, []
и ::
, вы имеют используете библиотечные функции для получения в любом месте со строками. 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"]
, потому что это ее префикс, а не потому, что она эквивалентна. С помощью s1 = s2
вы в конечном итоге проверяете, что что-то является допустимым суффикс, а не допустимым подстрока. Так что вам нужно изменить s1 = s2
на что-то более умное.
Возможно, вы можете создать вспомогательную функцию, которая определяет, является ли один список префиксом другого, и использовать ее здесь?
Что касается решения этого упражнения путем explode
объединения ваших строк в списки: это крайне неэффективно, настолько, что родственный язык Standard ML Ocaml имел explode
полностью удален из библиотеки:
The functions
explode
andimplode
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
уже существует, так что это решенная проблема. Но если бы это было не так, и хотелось бы написать это композиционно, и String.sub
не является мошенничеством (это обращение к символу в строке, сравнимое с сопоставлением начала и конца списка с шаблоном через x::xs
), то позвольте мне поощрять вам писать эффективный, компонуемый и функциональный код:
(* 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
, так и в isSubstring
, сделав 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