(defun trie-add (trie key-str val)
  (if (= (length key-str) 0)
      trie
    (let ((lst (split-string key-str "" t)))
      (rplacd (last lst) val)
      (trie-add::merge trie lst) )))
 
(defun trie-add::merge (trie lst)
  (cond ((null lst) trie)
	((null trie) lst)
	((atom (car trie))
	 (if (string= (car trie) (car lst))
	     (cons (car trie)
		   (trie-add::merge (cdr trie) (cdr lst)) )
	   (list (list trie lst)) ))
	(t
	 (let (r flg)
	   (setq r (mapcar #'(lambda (x)
			       (if (string= (car x) (car lst))
				   (progn
				     (setq flg t)
				     (trie-add::merge x lst) )
				 x ))
			   (car trie) ))
	   (cons (if flg r (cons lst (car trie)))
		 (cdr trie) ) ))))