1

我想用列表中的另一个子列表替换一个子 列表以实现以下结果：lista listblisto

let replace_sublist listo lista listb =

在 listo 中，如果有 sublist = lista，则将这个 sublist 替换为 listb。

我发现在 python 中实现了一个类似的问题。

链接： 用python中的另一个子列表替换一个子列表

有什么建议吗？谢谢。

4

3 回答 3

2 
type 'a strip_result =
| No_match
| Too_short
| Tail of 'a list

(** [try_strip li subli] tries to
    remove the prefix [subli] from the list [li] *)
let rec try_strip li subli = match li, subli with
  | _, [] -> Tail li
  | [], _ -> Too_short
  | hli::tli, hsub::tsub ->
    if hli <> hsub then No_match
    else try_strip tli tsub

let rec replace_sublist li from_sub to_sub =
  match li with
    | [] -> []
    | head::tail ->
      match try_strip li from_sub with
        | Too_short -> li
        | No_match -> head :: replace_sublist tail from_sub to_sub
        | Tail rest -> to_sub @ replace_sublist rest from_sub to_sub

let test =
  (* simple replace *)
  assert (replace_sublist [1;2;3;4] [2;3] [-2;-3] = [1;-2;-3;4]);
  (* multiple replace *)
  assert (replace_sublist [1;2;3;2;4] [2] [0] = [1;0;3;0;4]);
  (* stop while partial match *)
  assert (replace_sublist [1;2;3;4] [3;4;5] [0] = [1;2;3;4]);
  (* stop at match *)
  assert (replace_sublist [1;2;3;4] [3;4] [2;1] = [1;2;2;1]);
  (* tricky repeating sublist case *)
  assert (replace_sublist [2;2;3] [2;3] [0] = [2;0]);
  ()


(* tail-rec version: instead of concatenating elements before
   the recursive call
     head :: replace_sublist ...
     to_sub @ replace_sublist ...
   keep an accumulator parameter `acc` to store the partial result,
   in reverse order
     replace (t :: acc) ...
     replace (List.rev_append to_sub acc) ...
*)
let replace_sublist li from_sub to_sub =
  let rec replace acc li = match li with
    | [] -> List.rev acc
    | head::tail as li ->
      match try_strip li from_sub with
        | Too_short -> List.rev (List.rev_append li acc)
        | No_match -> replace (head :: acc) tail
        | Tail rest -> replace (List.rev_append to_sub acc) rest
  in replace [] li

PS：众所周知，这个算法可以通过在try_strip失败后移动来改进，不仅仅是移动到列表中的下一个元素，而是通过一些我们知道不能开始新匹配的元素。但是，要跳过的元素数量并不是简单的List.length from_sub - 1，它需要从模式结构中预先计算（这取决于“棘手的重复子列表”的存在）。这就是Knuth-Morris-Pratt算法。

于 2013-03-15T14:52:26.613 回答
1

你可以这样做：

let replace listo lista listb =
  let rec loop listo lista listb accu =
    match listo with
      [] -> List.rev accu
    | x :: xs ->
      if xs = lista then List.rev_append (x :: accu) listb
      else loop xs lista listb (x :: accu) in
  loop listo lista listb []

首先，您需要找到 sublist lista。找到此列表后，您只需还原累加器accu，然后附加listb

于 2013-03-15T09:57:35.423 回答
1

这本质上是一个子字符串搜索和替换。如果您的列表很长，您可能需要使用像Knuth-Morris-Pratt这样的奇特算法来避免二次比较。

（我打算写一些代码，bug gasche 已经做得很好了。）

于 2013-03-15T14:57:39.943 回答