0

I want to create a suffix tree from a given string. This is what I have came up with until now. Although some of the nodes are correctly added, some are missing. I suspect that my add_node_list is not working correctly but I can't find the reason why.

type stree = 
  | Tree of stree list 
  | Node of char * stree list
  | Leaf of char
;;

let str_explode s =
  let rec exp i l =
    if i < 0 then l else exp (i - 1) (s.[i] :: l)
  in
  exp (String.length s - 1) []
;;


let val_node n = 
  match n with
  | Leaf v -> v
  | Node(v, _) -> v
  | Tree l -> failwith "btich" 
;;

let rec add_node node char_list =
  let rec add_node_list node_list cl = 
    match cl with
    | [] -> []
    | hc::tc -> 
      match node_list with
      | [] -> 
        [Node (hc, add_node_list [] tc)]
      | hn::tn ->
        if val_node hn = hc then
          [add_node hn cl]
        else begin 
          (hn)::add_node_list [] cl
        end
  in
  match char_list with
  | [] -> node
  | hc::tc -> 
    match node with
    | Leaf _ -> node
    | Tree l -> Tree(add_node_list l char_list)
    | Node(c, l) -> 
      if c = hc then Node(c, add_node_list l tc)
      else Node(c, add_node_list l char_list)
;;


let arbre_suffixe str = 
  if not (String.ends_with str ~suffix:"#") 
  then failwith "texte invalid"
  else
    let char_list = str_explode str in
    let stree = Tree([]) in
    let rec aux tree ct =
      match ct with
      | [] -> tree
      | h::[] -> tree
      | h::t -> print_list ct; aux (add_node tree ct) t
    in aux stree char_list
;;

I tried with arbre_suffixe "ANANAS#" and I got:

Tree
 [Node ('A',
   [Node ('N',
     [Node ('A',
       [Node ('N', [Node ('A', [Node ('S', [Node ('#', [])])])]);
        Node ('S', [Node ('#', [])])])]);
    Node ('S', [Node ('#', [])])]);
  Node ('S', [Node ('#', [])])]

And I expect this answer:

Tree
 [Node ('A',
   [Node ('N',
     [Node ('A',
       [Node ('N', [Node ('A', [Node ('S', [Node ('#', [])])])]);
        Node ('S', [Node ('#', [])])])]);
    Node ('S', [Node ('#', [])])]);
  Node ('N',
   [Node ('A',
     [Node ('N', [Node ('A', [Node ('S', [Node ('#', [])])])]);
      Node ('S', [Node ('#', [])])])]);
  Node ('S', [Node ('#', [])]); Node ('S', [Node ('#', [])]); Node ('#', [])]
gasche
  • 31,259
  • 3
  • 78
  • 100
Steven
  • 3
  • 2
  • 1
    Suggest implementing `str_explode` as `let str_explode s = s |> String.to_seq |> List.of_seq` – Chris Nov 11 '22 at 16:43
  • what i'm trying to accomplish is something like this : ![](https://ibb.co/pdMqWcN) – Steven Nov 11 '22 at 16:55
  • 1
    @Steven incidentally, what you are trying to build is a [trie](https://en.wikipedia.org/wiki/Trie), not a [suffix tree](https://en.wikipedia.org/wiki/Suffix_tree). – jthulhu Nov 11 '22 at 17:17
  • Possibly useful reading: https://stackoverflow.com/questions/13893950/suffix-tree-and-tries-what-is-the-difference – Chris Nov 11 '22 at 18:12

0 Answers0