subsequence.ml

(* Search for all subsequences of s in a trie *)
let rec searchSubsequenceImpl 
  (s: char list) 
  (trie: trie)
: char list list = match s with
  | [] -> []
  | first_char :: rest_s ->
    let Node(children, _) = trie in
    (* Branch 1: Pick character *)
    let withChar =  if Trie.ChildList.mem first_char children
      then
        let nextNode = Trie.ChildList.find first_char children in
        let matches = searchSubsequenceImpl rest_s nextNode in
        let Node(_, next_is_word) = nextNode in
        let fullMatches = if next_is_word then ([] :: matches) else matches in
        (* Add the current matching character to all matches *)
        List.map (fun word -> first_char :: word) fullMatches
      else []
    in
    (* Branch 2: Do not pick character *)
    let withoutChar = searchSubsequenceImpl rest_s trie
    in
    (* Merge results *)
    withChar @ withoutChar

let searchSubsequence (s: string) (trie: trie): string list =
  let chars = BatString.to_list s in
  let results = searchSubsequenceImpl chars trie in
  List.map BatString.of_list results |> removeDuplicates