DouKaku?

#!/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)?)?)

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:])

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);
    }
}

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:])

(regexp-opt '("program"
              "programist"
              "programistic"
              "programma"
              "programmar"
              "programmatic"
              "programmatically"
              "programmatist"
              "programmer"))

(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)))

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())

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)?)?)

| 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)))$' "

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"
              ]

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());
    }
}

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