DouKaku?beta

challenge 文字列リストをTRIE Optimizeされた正規表現に

これは、実例を見た方が簡単だと思います。 CPANにRegexp::Assembleというモジュールがあるのですが、要はこれの簡易版を作って欲しいということです。私自身、同様のことを行うモジュールを過去にいくつか作っています(e.g Regexp::Optimizer)。

ここでは、文字列のリストを受け取って、それをTRIE化した正規表現に出来ればOKです。Regexp::AssembleやRegexp::Optimizerは正規表現を受け取ってそれをTrie化することも可能ですし、Perl 5.10では内部的にTrie Optimizationを行ったりするのですが、そこまでの機能は求めません。

なお、ここで言う「正規表現」は、必ずしもPerl互換のものである必要はありません。それがTrieになっていることをきちんと示せればOKです。

とはいうものの、Perl5互換になっていた方が、サポートしている環境が多くて有用性は高そうです。可能であればそうして下さい。

Dan the Regexp Assembler

see: Trie (en.wikipedia) 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#!/usr/local/bin/perl
use strict;
use warnings;
use Regexp::Assemble;

my $ra = Regexp::Assemble->new;
while(<>){
    chomp;
    next unless $_;
    $ra->add($_);
}
print $ra->re, "\n"
__END__

% grep program /usr/share/dict/words 
program
programist
programistic
programma
programmar
programmatic
programmatically
programmatist
programmer

% grep program /usr/share/dict/words | perl sample.pl 
(?-xism:program(?:m(?:a(?:ti(?:c(?:ally)?|st)|r)?|er)|ist(?:ic)?)?)
post comment

Posted feedbacks - Flatten

Nested Hidden

参考までに日本語版

トライ木 - Wikipedia： http://ja.wikipedia.org/wiki/%E3%83%88%E3%83%A9%E3%82%A4%E6%9C%A8


お題は要するに「文字列のリストを与えられたときに、それにマッチする正規表現を返せ」ということですね。

で、(?:foo|bar|baz)なんていうトリビアルな出力を許すと何も面白くないので、単語の頭が一致する場合はくっつけて(?:foo|ba[rz])とかにするということですよね？


素朴な方法で

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
import sys
import re

class Node(dict):
    def __init__(self, c, acceptable, children = None):
        if children is not None:
            super(Node, self).__init__(children)
        else:
            super(Node, self).__init__()

        self.c = c
        self.acceptable = acceptable

    def get_pattern(self):
        s = re.escape(self.c)
        trail = '|'.join(child.get_pattern() for child in self.itervalues())
        if trail:
            s += '(?:%s)' % trail
            if self.acceptable:
                s += '?'
        return s

    def optimize(self):
        children = dict()
        for child in self.itervalues():
            optimized = child.optimize()
            children[optimized.c] = optimized

        if len(children) == 1 and not self.acceptable:
            child = children.values()[0]
            c = self.c + child.c
            acceptable = child.acceptable
            return Node(c, acceptable, child)
        else:
            return Node(self.c, self.acceptable, children)

class Trie(object):
    def __init__(self, root = None):
        if root is None:
            self.root = Node('', False)
        else:
            self.root = root

    def add(self, word):
        node = self.root

        for c in word:
            if c not in node:
                node[c] = Node(c, False)
            node = node[c]
        node.acceptable = True

    def get_pattern(self):
        return self.root.get_pattern()

    def optimize(self):
        return Trie(self.root.optimize())

def main(args):
    import fileinput

    trie = Trie()
    for line in fileinput.input(args):
        word = line.strip()
        trie.add(word)

    trie = trie.optimize()
    print trie.get_pattern()

if __name__ == '__main__':
    main(sys.argv[1:])

あぁ、よく考えれば TRIE そのものをいじらなくてもいいな。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
import sys
import re

class Node(dict):
    def __init__(self, c, acceptable, children = None):
        if children is not None:
            super(Node, self).__init__(children)
        else:
            super(Node, self).__init__()

        self.c = c
        self.acceptable = acceptable

    def get_pattern(self):
        s = re.escape(self.c)
        if len(self) > 0:
            if len(self) == 1 and not self.acceptable:
                s += self.values()[0].get_pattern()
            else:
                s += '(?:%s)' % '|'.join(c.get_pattern() for c in self.itervalues())

            if self.acceptable:
                s += '?'
        return s

class Trie(object):
    def __init__(self, root = None):
        if root is None:
            self.root = Node('', False)
        else:
            self.root = root

    def add(self, word):
        node = self.root

        for c in word:
            if c not in node:
                node[c] = Node(c, False)
            node = node[c]
        node.acceptable = True

    def get_pattern(self):
        return self.root.get_pattern()

def main(args):
    import fileinput

    trie = Trie()
    for line in fileinput.input(args):
        word = line.strip()
        trie.add(word)

    print trie.get_pattern()

if __name__ == '__main__':
    main(sys.argv[1:])

とりあえず素朴に。例題データ読ませると「^program(?:|(?:ist(?:|ic)|m(?:a(?:|(?:r|ti(?:c(?:|ally)|st)))|er)))$」を吐きます。 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
using System;
using System.Collections.Generic;
using System.IO;
static class Program {
    public static void Main(String[] args) {
        // 行ごとに読み込んで
        List<string> words = new List<string>();
        using(StreamReader sr = new StreamReader(args[0])) {
            foreach(string line in sr.ReadToEnd().Split('\n', '\r')) {
                if (line != string.Empty && !words.Contains(line)) {
                    words.Add(line);
                }
            }
            words.Sort();
        }
        // 重複文字数をチェックして
        List<int> indexes = new List<int>(); {
            int[] itemp = new int[words.Count];
            for(int i = words.Count - 1; 1 <= i; i--) {
                int to = Math.Min(words[i - 1].Length, words[i].Length);
                for(int j = 0; j < to && words[i - 1][j] == words[i][j]; j++) {
                    itemp[i]++;
                }
            }
            indexes.AddRange(itemp);
        }
        // 重複文字数を多い順に並び替えて
        List<int> times = new List<int>(); {
            foreach(int cnt in indexes) {
                if (!times.Contains(cnt))
                    times.Add(cnt);
            }
            times.Sort();
            times.Reverse();
        }
        // 重複部分を削っていく
        foreach(int steps in times) {
            for(int i = words.Count - 1; 0 < i; i--) {
                if (indexes[i] == steps) {
                    words[i - 1] = string.Format("{0}(?:{1}|{2})",
                        words[i - 1].Substring(0, steps),
                        words[i - 1].Substring(steps),
                        words[i].Substring(steps));
                    words.RemoveAt(i);
                    indexes.RemoveAt(i);
                }
            }
        }
        string result = "^" + words[0] + "$";
        Console.WriteLine(result);
    }
}

こういうやり方もあるよ、ということで。

  1. 文字列を辞書順にソート
  2. 隣り合う文字列同士の共通接頭辞長(lcps)を計算

で、後はある範囲で lcp の最小値が共通接頭辞の長さで、最小値の位置でリストを分割すれば分割統治法でパターンを構築できると。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
import sys
import re

SLIM_RE = False

class RangeError(Exception):
    pass

def lcp(a, b):
    "returns length of longest common prefix"
    i = 0
    l = min(len(a), len(b))
    while i < l and a[i] == b[i]:
        i += 1
    return i

def min_index(l, first, last):
    "returns index of minimum value in [first:last]"
    if last - first <= 0:
        raise RangeError()
    i = first
    for j in xrange(first + 1, last):
        if l[j] < l[i]:
            i = j
    return i

def get_pattern(words, lcps, level, first, last):
    "get optimized regular expression from list of words which is sorted"
    if last - first == 1:
        return re.escape(words[first][level:])

    m = min_index(lcps, first, last - 1)
    prefix = words[first][level:lcps[m]]
    sub = (get_pattern(words, lcps, lcps[m], first, m + 1),
           get_pattern(words, lcps, lcps[m], m + 1, last))

    if SLIM_RE:
        pattern = '%s(?:%s)' % (re.escape(prefix), '|'.join(filter(bool, sub)))
        if len(words[m]) == lcps[m]:
            pattern += '?'
    else:
        pattern = '%s(?:%s|%s)' % (re.escape(prefix), sub[0], sub[1])
    return pattern

def main(args):
    import fileinput

    words = []
    for line in fileinput.input(args):
        words.append(line.strip())

    words.sort()
    lcps = [lcp(a, b) for a, b in zip(words[:-1], words[1:])]
    pattern = get_pattern(words, lcps, 0, 0, len(words))
    print pattern

    pat = re.compile(pattern)
    for word in words:
        if not pat.match(word):
            print >>sys.stderr, 'not match with %s' % word

if __name__ == '__main__':
    main(sys.argv[1:])


Emacs Lisp だと regexp-opt が要求通り(+α)のことをやってくれるようです。
ただ、backslash だらけな elisp の正規表現が返ります。

実行結果は以下。
"program\\(?:ist\\(?:ic\\)?\\|m\\(?:a\\(?:r\\|ti\\(?:c\\(?:ally\\)?\\|st\\)\\)?\
\\|er\\)\\)?"
1
2
3
4
5
6
7
8
9
(regexp-opt '("program"
              "programist"
              "programistic"
              "programma"
              "programmar"
              "programmatic"
              "programmatically"
              "programmatist"
              "programmer"))

> お題は要するに「文字列のリストを与えられたときに、それにマッチする正規表現を返せ」ということですね。

出力的にはYesですが、実装的にはNoです。 TRIE Optimizeされた正規表現は、そうでない正規表現と比べてかなりの速度差が出ます。詳しくは

のベンチマークの項をご覧ください。

Dan the Regular Expressionist 


ごちゃごちゃになってしまいました。
(空文字列の有無 (先頭 残り)...) で trie っぽいものを作ってますが、
データ構造が適当すぎたかも。
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
(defun classify (strings)
  (let ((a ()) (empty nil))
    (dolist (s strings (cons empty a))
      (if (string= s "")
          (setf empty t)
        (let* ((fst (elt s 0)) (rest (subseq s 1))
               (x (assoc fst a)))
          (if x (push rest (cdr x))
            (push `(,fst . (,rest)) a)))))))

;; TRIE ::= (data (char . TRIE)*)
(defun make-trie (strings)
  (let ((x (classify strings)))
    (cons (car x)
          (mapcar (lambda (a) (cons (car a) (make-trie (cdr a))))
                  (cdr x)))))

(defun make-regexp (trie)
  (cond ((and (null (car trie)) (null (cddr trie)))
         ;; (nil (c . subtrie)) => common prefix がある
         (format nil "~C~A" (caadr trie) (make-regexp (cdadr trie))))
        ((cdr trie)
         ;; (d (c . subtrie) ...) => common prefix なし
         (format nil "(?:~{~{~C~A~}~^|~})~@[?~]"
                 (mapcar (lambda (a) (list (car a) (make-regexp (cdr a))))
                         (cdr trie))
                 (car trie)))
        (t
         ;; 空文字列しかない
         "")))

(defun trie-optimize (strings) (make-regexp (make-trie strings)))


内部ではTRIEを使っていませんが、出力はお題でのサンプルと、
少なくともこの入力に関しては、同じになっています。

お題の解釈が出力だけを要求しているようにも読めるので、
とりあえず投稿します。

ちなみにカッコの中に'-xism'がある正規表現は
pythonのreモジュールでは使えないようです。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
import sys
import re

def f1(l):
  if len(l) == 1:
    return l[0]

  r = '^(?:%s%s)' % ('(?:'.join(list(l[0])), ')?' * (len(l[0])-1))
  b = []
  c = []
  for s in l:
    s = s.rstrip()
    m = re.findall(r, s)
    if m:
      b.append((m[0], s))
    else:
      c.append(s)

  a = min([t[0] for t in b])
  flg = bool([t[1] for t in b if a == t[1]])
  b = [t[1][len(a):] for t in b if len(t[1]) != len(a)]
  if b:
    a = '%s(?:%s)%s' % (a, f1(b), '?' if flg else '')
  if c:
    c = f1(c)
    a = '%s|%s' % ((a, c) if len(a) > len(c) else (c, a))
  return a

def f(l):
  return '(?-xism:%s)' % f1(l)
#  return '(?:%s)' % f1(l)

if __name__ == '__main__':
  print f(sys.stdin.readlines())


だいたい同じことを OCaml で。
パターンマッチのおかげで多少は読みやすくなったかも。
リストの破壊的操作ができないので Map を使ってみました。
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
open Printf

type trie = Node of bool * (char * trie) list

module M = Map.Make(struct type t = char let compare = Char.compare end)

let rec classify b map = function
  | [] -> b, map
  | ""::rest -> classify true map rest
  | str::rest ->
      let c, s = str.[0], String.sub str 1 (String.length str - 1) in
      let newmap =
        M.add c (s::try M.find c map with Not_found -> []) map in
        classify b newmap rest

let rec make_trie strings =
  let b, map = classify false M.empty strings in
    Node(b, M.fold (fun c strs al -> (c, (make_trie strs))::al) map [])

let rec make_regexp = function
  | Node(false, [c, trie]) -> sprintf "%c%s" c (make_regexp trie)
  | Node(b, (_::_ as alist)) ->
      let res =
        List.map (fun (c, t) -> sprintf "%c%s" c (make_regexp t)) alist in
      let re = String.concat "|" res in
        sprintf "(?:%s)%s" re (if b then "?" else "")
  | _ -> ""

let trie_optimize strings = make_regexp (make_trie strings)

1文字ずつのツリーを作って、子を1つしかもたない親に子をくっつけて、参考ページにあるようなTrieツリーにしました。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
import sys

def get_chr_tree(strs, before=""):
  index = len(before)
  s = set([str[index] for str in strs if len(str) > index and str[:index]==before])
  l = [get_chr_tree(strs, before+c) for c in s]
  return [before[-1]] + l if before else l[0]

def merge_chr(chr_tree):
  try:
    if len(chr_tree) == 2:
      return merge_chr([chr_tree[0]+chr_tree[1][0]] + chr_tree[1][1:])
    else: return [chr_tree[0]] + [merge_chr(tree) for tree in chr_tree[1:]]
  except IndexError:
    return chr_tree

def to_regexp(chr_tree):
  def make_regexp(chr_tree):
    if len(chr_tree) == 1: return chr_tree[0]
    else:
      hatena = "?" if [True for l in chr_tree[1:] if "\n" in l] else ""
      try:
        inner = "".join(["|" + make_regexp(tree) for tree in chr_tree[1:]])
      except IndexError:
        print "IndexError",chr_tree
        inner = ""
      return chr_tree[0] + "(?:" + inner + ")" + hatena

  return "(?-xism:" + make_regexp(chr_tree).replace("|\n", "").replace("\n", "").replace(":|", ":") + ")"

words = []
for line in sys.stdin: words.append(line)
chr_tree = get_chr_tree(words)
merged_chr_tree = merge_chr(chr_tree)
print to_regexp(merged_chr_tree) # => (?-xism:program(?:m(?:a(?:ti(?:c(?:ally)?|st)|r)?|er)|ist(?:ic)?)?)

しまった。言語の指定忘れてた。Pythonです。


Squeak Smalltalk で。

SiroKuro さんの #4105 を参考にさせて頂きました。最後、たたみ込みながら正規表現を生成するところはたいへん小気味よいですね。 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| assemble |
assemble := [:words |
    | prefixSizes |
    words := words sort.
    prefixSizes := words overlappingPairsCollect: [:aa :bb |
        | shorterSize found |
        shorterSize := aa size min: bb size.
        found := (1 to: shorterSize) findFirst: [:idx | (aa at: idx) ~= (bb at: idx)].
        found isZero ifTrue: [shorterSize] ifFalse: [found - 1]].
    prefixSizes asSet asArray sort reverseDo: [:idx |
        | found |
        [(found := prefixSizes lastIndexOf: idx) > 0] whileTrue: [
            words at: found put: ('{1}(?:{2}|{3})' format: {
                (words at: found) first: idx.
                (words at: found) allButFirst: idx.
                (words at: found + 1) allButFirst: idx}).
            words := words copyWithoutIndex: found + 1.
            prefixSizes := prefixSizes copyWithoutIndex: found]].
    '^', words first, '$'].

assemble value: #(
    program
    programist
    programistic
    programma
    programmar
    programmatic
    programmatically
    programmatist
    programmer)

"=> '^program(?:|(?:ist(?:|ic)|m(?:a(?:|(?:r|ti(?:c(?:|ally)|st)))|er)))$' "

なんだかメタキャラクタのエスケープを全くしていないコードが目立つような。 まずくないですかね？


#4259 の指摘を受けて、とりあえず Regex.Escape 挟んでみました。 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
--- trie.cs.old Tue Nov 20 01:20:52 2007
+++ trie.cs     Tue Nov 20 01:21:24 2007
@@ -8,7 +8,7 @@
         using(StreamReader sr = new StreamReader(args[0])) {
             foreach(string line in sr.ReadToEnd().Split('\n', '\r')) {
                 if (line != string.Empty && !words.Contains(line)) {
-                    words.Add(line);
+                    words.Add(System.Text.RegularExpressions.Regex.Escape(line)
);
                 }
             }
             words.Sort();


Text.RegexモジュールではデフォルトではPOSIXの正規表現をつかっている．
ここではそれにしたがった正規表現文字列を生成する．
メタ文字のエスケープもしたつもり．

実行結果
*Main> putStrLn $ oregex (unfoldTree phi sample) ""
program(ist(ic)?|m(a(r|ti(c(ally)?|st))?|er))?

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
import Data.List
import Data.Tree

type Trie = Tree (Bool,String)

eqapp f x y = f x == f y

lcp :: [String] -> (String, [String])
lcp [] = ("",[])
lcp xxs@(x:xs) 
 = if null x 
      then ("",xxs)
      else if all (isPrefixOf [head x]) xs 
              then case lcp (map tail xxs) of
                     (ps,yys) -> (head x:ps,yys)
              else ("",xxs)


phi :: [String] -> ((Bool,String), [[String]])
phi [x] = ((False,x), [])
phi xxs  = case lcp xxs of
 (ps,"":ys) -> ((True,ps), groupBy (eqapp head) ys)
 (ps,yys)   -> ((False,ps),groupBy (eqapp head) yys)

oregex :: Trie -> ShowS
oregex (Node (p,s) [])
 | p         = showString (escape s) . showString "?"
 | otherwise = showString (escape s)
oregex (Node (p,s) cs)
 | p         = (showString (escape s) .) $ (. showString "?") $ paren $ foldr (.) id (intersperse (showString "|") (map oregex cs))
 | otherwise = (showString (escape s) .) $ paren $ foldr (.) id (intersperse (showString "|") (map oregex cs))

paren :: ShowS -> ShowS
paren s = showString "(" . s . showString ")"

metaChars = "\\|[](){}.*+?^$"
escapeMeta c | elem c metaChars = '\\':[c]
             | otherwise        = [c]

escape = concatMap escapeMeta

sample = sort ["program"
              ,"programist"
              ,"programistic"
              ,"programma"
              ,"programmar"
              ,"programmatic"
              ,"programmatically"
              ,"programmatist"
              ,"programmer"
              ]

気付いていながらエスケープしないコードを投稿してしまった人です。

単に、まあいいかなと思ってそのままにしました。 お題の趣旨はどうやって trie を作るかで、問題文が細かいところにはあまり拘らないという感じだったので。

ただ、改めて考えると一応正規表現を作れという問題ですから、よくなかったかもしれません。少なくとも気付いてたなら投稿時に言及しとくべきでしたね。


引数で与えられた文字列（のみ）にマッチする正規表現を生成します。生成される正規表現はPerl互換のはずです（Javaで動作する事は確認してあります）。

program
programist
programistic
programma
programmar
programmatic
programmatically
programmatist
programmer
を与えた場合は、
program(?:|ist(?:|ic)|m(?:a(?:|r|ti(?:c(?:|ally)|st))|er))
を生成します。

＃Javaの総称で再帰的なデータ構造を表現する事はできないのでしょうか（この例ではキャストで逃げています）。 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
import java.util.*;

@SuppressWarnings("unckecked")
public class Trie {
    public static final String MUST_ESCAPE = "()[]\\.+*?|";
    private Map<Character, Map> trie = new TreeMap<Character, Map>();
    public void add(String str) {
        Map<Character, Map> t = trie;
        for (char c : str.toCharArray()) {
            if (t.containsKey(c)) {
                t = (Map<Character, Map>)t.get(c);
            } else {
                Map<Character, Map> t2 = new TreeMap<Character, Map>();
                t.put(c, t2);
                t = t2;
            }
        }
        t.put('\0', null);
    }
    public String toRegex() {
        return toRegex(trie).toString();
    }
    private StringBuilder toRegex(Map<Character, Map> t) {
        StringBuilder sb = new StringBuilder();
        Set<Character> keys = t.keySet();
        if (keys.size() > 1)
            sb.append("(?:");
        Iterator<Character> i = keys.iterator();
        while (i.hasNext()) {
            char c = i.next();
            if (c != '\0') {
                if (MUST_ESCAPE.indexOf(c) >= 0)
                    sb.append('\\');
                sb.append(c);
                sb.append(toRegex(t.get(c)));
            }
            if (i.hasNext())
                sb.append('|');
        }
        if (keys.size() > 1)
            sb.append(")");
        return sb;
    }
    public static void main(String[] args) {
        Trie t = new Trie();
        for (String str : args) {
            t.add(str);
        }
        System.out.println(t.toRegex());
    }
}

連想配列を使って普通に木を作る方法で。

標準ライブラリ(std.regexp)では後方参照なしのグルーピングがサポートされないので、普通の括弧にしました。

program(ist(ic)?|m(a(r|ti(c(ally)?|st))?|er))? 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
import std.stdio, std.string, std.utf;

class Trie {
    private struct Node {
        Node*[dchar] nodes;
        bool matchTail;
        
        const string toString() {
            if(!nodes.length) return "";
            string[] patterns;
            foreach(c, node; this.nodes) {
                patterns ~= quotemeta(toUTF8([c])) ~ node.toString();
            }
            string pattern = patterns.join("|");
            if(nodes.length == 1) {
                return matchTail ? "(" ~ pattern ~ ")?" : pattern;
            } else {
                return "(" ~ pattern ~ ")" ~ (matchTail ? "?" : "");
            }
        }
    }
    
    private Node tree;
    
    this() { }
    
    this(const(string)[] words) {
        foreach(word; words) {
            this.addWord(word);
        }
    }
    
    void addWord(string word) {
        auto node = &this.tree;
        foreach(dchar c; word) {
            if(auto p = c in node.nodes) {
                node = *p;
            } else {
                node = node.nodes[c] = new Node;
            }
        }
        node.matchTail = true;
    }
    
    const string toString() {
        return tree.toString();
    }
}

private string quotemeta(string str) {
    string result;
    foreach(c; str) {
        switch(c) {
            case '.': case '*': case '+': case '?':
            case '^': case '$': case '{': case '}':
            case '[': case ']': case '(': case ')':
            case '|':
                result ~= ['\\', c];
                break;
            default:
                result ~= c;
        }
    }
    return result;
}

void main(){
    auto words = `program
programist
programistic
programma
programmar
programmatic
programmatically
programmatist
programmer`.splitlines();
    writeln(new Trie(words));
}