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

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

1 голос
/ 12 марта 2019

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

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

Ответы [ 2 ]

1 голос
/ 12 марта 2019

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

В вашем рекурсивном случае вы добавляете 1 к рекурсивному результату, даже если рекурсивное приложение не нашло подстроку и вернуло -1,Вы должны проверить, равен ли результат -1, прежде чем добавлять 1.

Во второй строке вы проверяете, равны ли две строки.Если вы сделаете это, вы найдете подстроку, только если строка заканчивается этой подстрокой.Итак, что вы действительно хотите сделать в строке 2, это проверить, начинается ли s2 с s1.Я бы порекомендовал вам написать вспомогательную функцию, которая выполняет этот тест.Для этой вспомогательной функции вы действительно можете использовать explode, а затем рекурсивно проверить, идентичны ли первые символы списков.Если у вас есть эта вспомогательная функция, используйте ее в строке 2 вместо теста на равенство.

0 голосов
/ 12 марта 2019

Я не должен использовать какие-либо встроенные функции, такие как 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 полностью удалил из библиотеки:

Функции explode и implode были в более старых версиях Caml, но мы исключили их из OCaml, потому что они поддерживают неэффективный код. Как правило, плохая идея рассматривать строку как список символов, и рассматривать ее как массив символов гораздо лучше подходит для реальной реализации.

Итак, во-первых, 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
...