Определение того, является ли строка подстрокой другой в Sml без библиотечных функций

Я пытаюсь написать функцию, которая 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);

Я думаю об использовании вспомогательной функции, которая взрывает строки, а затем, возможно, сравнивает их, но я не могу понять, как заставить это работать.

В чем разница между методом "==" и equals()
В чем разница между методом "==" и equals()
Это один из наиболее часто задаваемых вопросов новичкам на собеседовании. Давайте обсудим его на примере.
Замена символа по определенному индексу в JavaScript
Замена символа по определенному индексу в JavaScript
В JavaScript существует несколько способов заменить символ в строке по определенному индексу.
1
0
1 041
2
Перейти к ответу Данный вопрос помечен как решенный

Ответы 2

Это уже действительно хорошее начало, но есть небольшие проблемы:

В вашем рекурсивном случае вы добавляете 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 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 уже существует, так что это решенная проблема. Но если бы это было не так, и хотелось бы написать это композиционно, и 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

Другие вопросы по теме