DouKaku?

implement Longtail;

include "sys.m";
    sys: Sys;
include "draw.m";
include "bufio.m";
    bufio: Bufio;
    Iobuf: import bufio;
include "string.m";
    str: String;

Longtail: module
{
    init: fn(ctxt: ref Draw->Context, argv: list of string);
};

Word: adt
{
    s: string;
    used: int;
};

MAXRUNE: con 16rffff;

tab := array[MAXRUNE] of list of ref Word;

init(nil: ref Draw->Context, nil: list of string)
{
    sys = load Sys Sys->PATH;
    bufio = load Bufio Bufio->PATH;
    str = load String String->PATH;

    install(sys->fildes(0));

    wstart := ref Word("シリトリ", 0);
    result := chain(wstart);
    for(p := result; p != nil; p = tl p)
        sys->print("%s\n-> ", (hd p).s);
    sys->print("END\n");
}

install(fd: ref Sys->FD)
{
    fin := bufio->fopen(fd, bufio->OREAD);
    while((t := fin.gett(" \t\n")) != nil){
        (t, nil) = str->splitl(t, " \t\n");
        if(t == "")
            continue;
        tab[t[0]] = ref Word(t, 0) :: tab[t[0]];
    }
}

chain(w: ref Word): list of ref Word
{
    longest: list of ref Word;

    w.used = 1;
    lastc := w.s[len w.s - 1];
    for(p := tab[lastc]; p != nil; p = tl p){
        w1 := hd p;
        if(w1.used)
            continue;
        t := chain(w1);
        if(len t > len longest)
            longest = t;
    }
    w.used = 0;
    return w :: longest;
}

use strict;
use warnings;
use utf8;

use Encode;

my $input_enc = shift || 'utf-8';
my $output_enc = shift || 'cp932';

my $words = readwords();
my $table = maketable($words);

my $total = @$words;
my $count = 0;
#my $next = $words->[int rand $total];
my $next = $words->[0];
erase($next, $table);
print encode($output_enc, "begin from [$next]\n");
while ( 1 ) {
  ++$count;
  last if is_stop($next);
  my $prev = $next;

  $next = draw_next($prev, $table);
  last if !defined $next;

  print encode($output_enc, "next -> [$next]\n");
}    
print encode($output_enc, "END ($count/$total)\n");

sub readwords
{
  [ map { tr/ア-ン/あ-ん/; $_ }
    map { decode($input_enc, $_) }
    map { chomp; split /\s+/ } <STDIN> ];
}    

sub maketable
{
  my $words = shift;

  my %table;
  for my $w ( @$words ) {
    my $first = substr $w, 0, 1;

    $table{$first} = [0,0,[]] if !exists $table{$first};

    ++$table{$first}[0];
    if ( is_stop($w) ) {
      ++$table{$first}[1];
    }
    push @{$table{$first}[2]}, $w;
  }
  \%table;
}

sub erase
{
  my ($word, $table) = @_;

  my $first = substr $word, 0, 1;

  --$table->{$first}[0];
  if ( is_stop($word) ) {
    --$table->{$first}[1];
  }

  @{$table->{$first}[2]} = grep { $_ ne $word } @{$table->{$first}[2]};
}

sub draw_next
{
  my ($word, $table) = @_;
  my $next = get_candidate($word, $table)->[0];
  erase($next, $table) if defined $next;
  $next;
}

sub is_stop
{
  my $word = shift;
  (length($word)>1 ? substr $word, -1, 1 : $word) eq 'ん';
}

sub get_candidate
{
  my ($word, $table) = @_;

  my $last = substr $word, -1, 1;

  my $candidate = [undef, -1];
  for my $next ( @{$table->{$last}[2]} ) {
    my $next_last = substr $next, -1, 1;

    my $point = exists $table->{$next_last}
    ? $table->{$next_last}[0] - $table->{$next_last}[1]
    : 0;
    if ( $point > $candidate->[1] ) {
      $candidate = [$next, $point];
    }
  }
  $candidate;
}

import java.io.*;
import java.util.*;

/**
 * いちばん長いしりとり
 */
public class TheLongestSiritori {
    
    // 単語
    private static class Word {
        String text;    // 単語の文字列
        boolean used;    // 使用中フラグ
    }

    // 頭文字をキーとする単語の索引。
    private static Map<String, List<Word>> index = new HashMap<String, List<Word>>();
    
    /**
     * メインルーチン
     * @param args 最初の引数は単語ファイルの名前
     */
    public static void main( String[] args ) {
    
        ////////////////////////////////////////////////////////////
        // 引数から単語ファイルの名前を取得する。
        ////////////////////////////////////////////////////////////
        
        // 引数に単語ファイルの名前が指定されていることを確認する。
        if ( args.length < 1 ) {
            // 指定されていない
            System.err.println( "引数に単語ファイルの名前を指定してください。"  );
            return;
        }
        
        // 引数からファイル名を取得する。
        String fileName = args[0];
        
        ////////////////////////////////////////////////////////////
        // 単語ファイルを読み込み、単語の一覧を作成する。
        ////////////////////////////////////////////////////////////
        
        List<Word> wordList = new ArrayList<Word>();
        BufferedReader reader = null;
        try {
            // 単語ファイルを開く。
            reader = new BufferedReader( new FileReader( fileName ) );
            
            // 単語ファイルの行ごとに以下を繰り返す。
            String line;
            while ( ( line = reader.readLine() ) != null ) {
                // 行が空でないことを確認する。
                if ( line.length() > 0 ) {
                    // 行の内容を単語の一覧に追加する。
                    Word word = new Word();
                    word.text = line;
                    word.used = false;
                    wordList.add( word );
                }
            }
            
        } catch ( IOException e ) {
            // 入力エラー:
            System.err.println( "単語ファイルを正常に読み込めませんでした。ファイル名前=[" + fileName + "]"  );
            return;
            
        } finally {
            if ( reader != null ) {
                try {
                    // 単語ファイルを閉じる。
                    reader.close();
                } catch ( IOException e ) {
                    /* 無視 */
                }
            }
        }
        
        ////////////////////////////////////////////////////////////
        // 頭文字をキーとした単語の索引を作成する。
        ////////////////////////////////////////////////////////////
        
        index = new HashMap<String, List<Word>>();

        // 単語の一覧中のすべての単語について、以下を繰り返す。
        for ( int i = 0; i < wordList.size(); ++i ) {
            Word word = wordList.get( i );
            // 単語の頭文字を取得する。
            String first = word.text.substring( 0, 1 );
            
            List<Word> container;
            // 同一の頭文字の単語が、索引に格納済みであることを確認する。
            if ( ! index.containsKey( first ) ) {
                // 同一の頭文字の単語が、まだ格納されていない:
                
                // 頭文字に対応する単語格納リストを作成する。
                container = new ArrayList<Word>();
                index.put( first, container );
            } else {
                // 頭文字に対応する単語格納リストを作成する。
                container = index.get( first );
            }

            // 単語格納リストに単語を追加する。
            container.add( word );
        }
        
        ////////////////////////////////////////////////////////////
        // しりとりをする。
        ////////////////////////////////////////////////////////////
        
        // 最初の単語をランダムに決める。
        int rnd = new Random().nextInt( wordList.size() );
        Word start = wordList.get( rnd );
        
        // 最長のしりとり結果(逆順)を取得する。
        List<String> longest = getLongest( start );
        
        // しりとり結果を反転する。
        Collections.reverse( longest );
        
        ////////////////////////////////////////////////////////////
        // 結果を表示する。
        ////////////////////////////////////////////////////////////
        
        for ( int i = 0; i < longest.size(); ++i ) {
            System.out.println( ( i + 1 ) + ": " + longest.get( i ) );
        }
    }
    
    /*
     * 最長のしりとり結果(逆順)を取得する。
     * @param 単語
     * @return 最長のしりとり結果(逆順)
     */
    public static List<String> getLongest( Word word ) {
        // 単語使用中フラグをオンにする。
        word.used = true;
        
        // 単語の末尾の文字を取得する。
        String text = word.text;
        int length = text.length();
        String last = text.substring( length - 1, length );
        
        List<String> longest = new ArrayList<String>();
        
        // 索引に末尾の文字が含まれていることを確認する。
        if ( index.containsKey( last ) ) {

            ////////////////////////////////////////////////////////////
            // 末尾の文字の後に続く、最長のしりとり結果を見つける。
            ////////////////////////////////////////////////////////////

            // 末尾の文字から始まるすべての単語について、以下を繰り返す。
            List<Word> container = index.get( last );
            for ( int i = 0; i < container.size(); ++i ) {
                Word nextWord = container.get( i );
                // 単語使用中フラグがオフであることを確認する。
                if ( ! nextWord.used ) {
                    // しりとり結果を取得する。
                    List<String> temp = getLongest( nextWord );
                    // 最長のしりとり結果を見つける。
                    if ( temp.size() > longest.size() ) {
                        longest = temp;
                    }
                }
            }
        }
        
        // 単語をしりとり結果に追加する。
        longest.add( text );
        
        // 単語使用中フラグをオフにする。
        word.used = false;

        return longest;
    }
}

import java.io.*;
import java.util.*;

public class Sample277 {
    static class Word {
        /// キーは全てカタカナに正規化
        public static String convertHiraganaToKatakana(String s) {
            StringBuilder builder = new StringBuilder(s);
            for (int index = 0; index < builder.length(); index++) {
                char c = builder.charAt(index);
                if ('ぁ' <= c && c <= 'ん') {
                    builder.setCharAt(index, (char)(c - 'ぁ' + 'ァ'));
                }
            }
            return builder.toString();
        }

        /// 拗音・促音・濁点などのリスト
        private static final Set<Character> anomalyLetters_ = new HashSet<Character>();
        {
            anomalyLetters_.add('ぁ');
            anomalyLetters_.add('ぃ');
            anomalyLetters_.add('ぅ');
            anomalyLetters_.add('ぇ');
            anomalyLetters_.add('ぉ');
            anomalyLetters_.add('っ');
            anomalyLetters_.add('ゃ');
            anomalyLetters_.add('ゅ');
            anomalyLetters_.add('ょ');
            anomalyLetters_.add('ァ');
            anomalyLetters_.add('ィ');
            anomalyLetters_.add('ゥ');
            anomalyLetters_.add('ェ');
            anomalyLetters_.add('ォ');
            anomalyLetters_.add('ッ');
            anomalyLetters_.add('ャ');
            anomalyLetters_.add('ュ');
            anomalyLetters_.add('ョ');
            anomalyLetters_.add('゛');
            anomalyLetters_.add('゜');
        }

        public final String s;
        public final String first;
        public final String last;
        private boolean used_ = false;

        public Word(String s) {
            this.s = s;
            first = convertHiraganaToKatakana(getFirstLetter(s));
            last = convertHiraganaToKatakana(getLastLetter(s));
        }
        // しりとりのキーとしての最初の音
        private String getFirstLetter(String s) {
            if (anomalyLetters_.contains(s.charAt(1))) {
                return s.substring(0, 2);
            }
            return s.substring(0, 1);
        }
        // しりとりのキーとしての最後の音
        private String getLastLetter(String s) {
            int lastStartIndex = s.length() - 1;
            int lastEndIndex = s.length();
            char c = s.charAt(lastStartIndex);
            if (c == 'ー' || c == 'ー') {
                lastStartIndex--;
                lastEndIndex--;
                c = s.charAt(lastStartIndex);
            }
            if (anomalyLetters_.contains(c)) {
                lastStartIndex--;
            }
            return s.substring(lastStartIndex, lastEndIndex);
        }

        public boolean isUsed() {
            return used_;
        }
        public void setUsed(boolean used) {
            used_ = used;
        }


        @Override
        public boolean equals(Object obj) {
            if (!this.getClass().equals(obj.getClass())) {
                return false;
            }
            Word other = (Word) obj;
            return this.s.equals(other.s);
        }
        @Override
        public int hashCode() {
            return s.hashCode();
        }
    }


    private final Map<String, Set<Word>> wordMap_ = new HashMap<String, Set<Word>>();

    public Sample277() {
    }

    public void addWord(String s) {
        Word word = new Word(s);
        Set<Word> set = wordMap_.get(word.first);
        if (set == null) {
            set = new HashSet<Word>();
            wordMap_.put(word.first, set);
        }
        set.add(word);
    }


    public List<String> getLongest(String start) {
        Word w = new Word(start);
        return getLongestR(w);
    }
    public List<String> getLongestR(Word w) {
        List<String> result = new LinkedList<String>();
        w.used_ = true;
        Set<Word> set = wordMap_.get(w.last);
        Set<String> firstLetter = new HashSet<String>();
        if (set != null) {
            for (Word word: set) {
                if (word.isUsed()) {
                    continue;
                }
                if (firstLetter.contains(word.last)) {
                    continue;
                }
                firstLetter.add(word.last);
                
                List<String> list = getLongestR(word);
                if (result.size() < list.size()) {
                    result = list;
                }
            }
        }
        w.used_ = false;
        result.add(0, w.s);
        return result;
    }


    public static List<String> loadFile(String path) throws FileNotFoundException {
        List<String> result = new ArrayList<String>();
        Scanner scanner = new Scanner(new File(path), "MS932");
        while (scanner.hasNext()) {
            result.add(scanner.next());
        }
        scanner.close();
        return result;
    }

    public static void main(String[] args) throws IOException {
        List<String> strings = loadFile("fam55_10.txt");
        System.out.println("input count: " + strings.size());

        Sample277 sample = new Sample277();
        for (String s: strings) {
            sample.addWord(s);
        }

        long start = System.currentTimeMillis();
        List<String> result = sample.getLongest("しりとり");
        long elapse = System.currentTimeMillis() - start;
        System.out.println("elapse: " + elapse + "(ms)");

        System.out.println("max length: " + result.size());
        for (String s: result) {
            System.out.println(s);
        }
    }
}

module Main where
import System.Environment (getArgs)
import Prelude hiding (putStrLn, putStr, print, readFile)
import System.IO.UTF8 (putStrLn, putStr, print, readFile)
import Codec.Binary.UTF8.String (encodeString)
import Data.List (delete, find, maximumBy)
import Control.Monad (msum, MonadPlus(..), filterM)

dic :: IO [String]
dic = do  src <- readFile "words.dat"
          return $ words src

f # g = \a b -> g (f a) (f b)

main = do wds <- dic
          args <- getArgs
          let mb = "-a" `elem` args
              sh :: (Functor m, MonadPlus m, Eq (m [String])) => m [String]
              sh = shiritori (head wds) wds
          if mb
            then pr sh
            else printStrList $ maximumBy (length#compare) sh

pr :: Maybe [String] -> IO ()
pr = maybe (return ()) printStrList
showStrList xs = "[" ++ concatMap (++",") xs ++ "]"
printStrList = putStrLn . showStrList

shiritori :: (Functor m, MonadPlus m, Eq (m [String])) => String -> [String] -> m [String]
shiritori w ws = (do  let wd' = w `delete` ws
                      ns <- nextWords w wd'
                      shiritori ns wd') `hoge` w

a `hoge` t = if a == mzero then return [t] else fmap (t:) a

nextWords :: (MonadPlus m) => String -> [String] -> m String
nextWords wd list = do
  xs <- filterM (\a -> return (last wd == head a)) list
  msum $ map return xs

#!/usr/bin/python
# -*- coding: utf-8 -*-
# http://ja.doukaku.org/277/

import sys

ENCODING = 'utf8'


class Word:

    def __init__(self, word):
        self._word = word
        self._trailwords = []

    def word(self):
        return self._word

    def head_char(self):
        return self.word()[0]

    def tail_char(self):
        return self.word()[-1]

    def is_trailword(self, trailword):
        return self.tail_char() == trailword.head_char()

    def is_last_word(self):
        return self.tail_char() in (u'ん', u'ン')

    def append_trailword_list(self, trailword):
        if not self.is_last_word() and self.is_trailword(trailword):
            self.trailwords().append(trailword)

    def trailwords(self):
        return self._trailwords

    def num_trailwords(self):
        return len(self.trailwords())


class WordQueue:

    def __init__(self, words=[]):
        self._words = words
        self._queue = []
        self._walk_step = 0

    def words(self):
        return self._words

    def num_words(self):
        return len(self.words())

    def append(self, word):
        self._words.append(word)

    def queue(self):
        return self._queue

    def queue_len(self):
        return len(self.queue())

    def walk(self):
        return self._walk(self.words(), [])

    def _walk(self, words, queue):
        self._walk_step += 1
        if self.walk_step() % 1000 == 0:
            print '(%d, %d, %d)' % (self.walk_step(), self.num_words(),
                                    self.queue_len())
        for word in words:
            if word in queue or word in self.queue():
                continue
            queue.append(word)
            self._walk(word.trailwords(), queue)
        else:
            if len(queue) > self.queue_len():
                self._queue = map(None, queue)
            if len(queue) > 0:
                queue.pop()

    def walk_step(self):
        return self._walk_step


if __name__ == '__main__':
    q = WordQueue()
    for line in sys.stdin:
        for item in line.decode(ENCODING).strip().split('\t'):
            if item is None or item == '':
                continue
            new_word = Word(item)
            for word in q.words():
                word.append_trailword_list(new_word)
                new_word.append_trailword_list(word)
            q.append(new_word)
    q.walk()

    for (i, w) in enumerate(q.queue()):
        print '%s %s %d' % (id(w), w.word(), w.num_trailwords())

    print 'number of words : %d' % q.num_words()
    print 'queue length    : %d' % q.queue_len()
    print 'number of step  : %d' % q.walk_step()

# vim : fileencoding=utf8

#!/usr/bin/env perl

use strict;
use warnings;
use utf8;
use List::Util qw/reduce/;

my @katakanas = split //, 'アイウエオカキクケコガキグゲゴサシスセソ'
                        . 'ザジズゼゾタチツテトダヂヅデドナニヌネノ'
                        . 'ハヒフヘホバビブベボパピプペポマミムメモ'
                        . 'ヤユオワヲン';

sub head_and_tail($) {
  my $word = shift;
  $word =~ tr/ァィゥェォッャュョヮ/アイウエオツヤユヨワ/;
  $word =~ s/ー$//;
  (substr($word, 0, 1), substr($word, -1, 1));
}

sub longest_chain(\%;$);
sub longest_chain(\%;$) {
  no warnings qw/recursion/;
  my ($dict, $word) = @_;
  my @words = defined $word
              ? ($word)
              : map { map { $_->[0] } values %$_ } values %$dict;
  reduce {
    @$a > @$b ? $a : $b;
  } ([],
     map {
       my $word = $_;
       my (undef, $next_head) = head_and_tail $word;
       map {
         my $available_words = $dict->{$next_head}{$_};
         my $next_word = pop @$available_words;
         my $chain = longest_chain(%$dict, $next_word);
         push @$available_words, $next_word;
         unshift @$chain, $word;
         $chain;
       } grep { @{ $dict->{$next_head}{$_} } } keys %{ $dict->{$next_head} };
     } @words);
}

binmode STDOUT, ':utf8';
open my $words_file, '<:encoding(shiftjis)', shift or die $!;
my @words = (map { chomp; split /\s+/ } <$words_file>);
$#words = shift() - 1 if @ARGV;
my %dict;
for my $word (@words) {
  my ($head, $tail) = head_and_tail $word;
  $dict{$head}{$tail} = [] unless exists $dict{$head}{$tail};
  push @{ $dict{$head}{$tail} }, $word;
}
local ($,, $\) = (' -> ', "\n");
print @{ longest_chain(%dict) };

| url allWords intermediates dict results words |
url := 'http://www.ais.riec.tohoku.ac.jp/lab/wordlist/fam55_40.txt' asUrl.
allWords := (url retrieveContents contents convertFromEncoding: #sjis) subStrings.
results := (Array new: 10 withAll: #()) asSortedCollection: [:a :b | a size > b size].
intermediates := (words := allWords shuffled first: 100) collect: [:each | OrderedCollection with: each].
dict := words groupBy: [:each | each first] having: [:group | true].
[intermediates notEmpty] whileTrue: [
    | nextGen |
    nextGen := OrderedCollection new.
    (intermediates groupBy: [:each | each last last] having: [:group | true]) associationsDo: [:assoc |
        | nexts |
        nexts := dict at: assoc key ifAbsent: [#()].
        assoc value do: [:each |
            (nexts difference: each) ifEmpty: [results add: each; removeLast] ifNotEmptyDo: [:cands |
                cands do: [:next | nextGen add: (each copyWith: next)]]]].
    (intermediates := nextGen) size printString, ' ' displayAt: 0 asPoint].
^results first asArray

(defun first-char (s) (char s 0))
(defun last-char (s) (char s (1- (length s))))

(defun longer (list1 list2)
  (loop for x = list1 then (cdr x) and y = list2 then (cdr y)
     if (null x) return list2
     if (null y) return list1))

(defparameter *word-table* nil)

(defun get-next-words (c) (gethash c *word-table*))

(defun make-table (word-list key)
  (let ((h (make-hash-table)))
    (loop for w in word-list do (push w (gethash (funcall key w) h)))
    h))

(defun longest (word-list)
  (let ((*word-table* (make-table word-list #'first-char)))
    (reverse (reduce #'longer word-list :key #'longest-path-from))))

(defun longest-path-from (word)
  (search-path (list word)))

(defun search-path (path)
  (let* ((w (car path))
         (c (last-char w))
         (words (set-difference (get-next-words c) path)))
    (if words
        (reduce #'longer words
                :key (lambda (next) (search-path (cons next path))))
        path)))

import java.io.InputStreamReader;
import java.util.*;

public class Shiritori3 {
    public static void main(String[] args) throws Exception {
        long startTime = System.nanoTime();
        final Scanner scanner = new Scanner(new InputStreamReader(
                Shiritori.class.getResourceAsStream("Words_jp.txt"), "UTF-8"));
        new Shiritori3(scanner).analyze();
        System.out.printf("%f [sec]%n", ((double)System.nanoTime() - startTime) / 100000000);
    }

    Map<Character, Node> nodes;

    public Shiritori3(Scanner scanner) {
        nodes = new HashMap<Character, Node>();
        init(scanner);
    }

    private void init(Scanner scanner) {
        while (scanner.hasNext()) {
            String edge = scanner.next();
            char head = headChar(edge);
            char tail = tailChar(edge);
            if (!nodes.containsKey(head)) nodes.put(head, new Node(head));
            if (!nodes.containsKey(tail)) nodes.put(tail, new Node(tail));
            nodes.get(head).addGoOutEdge(edge);
            nodes.get(tail).addCominEdge(edge);
        }
        scanner.close();
    }

    public void analyze() {
        Set<Node> noflows = new HashSet<Node>();
        Set<Node> flows = new HashSet<Node>();
        for (Node node : nodes.values())
            if (node.hasCapacity()) flows.add(node);

        List<LinkedList<String>> pathList = new ArrayList<LinkedList<String>>();

        while (!flows.isEmpty()) {

            // 初期ノードの選択により、結果が変化する
            Node head = flows.toArray(new Node[0])[new java.util.Random().nextInt(flows.size())];
            Node tail = head;

            LinkedList<String> path = new LinkedList<String>();
            pathList.add(path);

            while (head.hasCapacity() || tail.hasCapacity()) {
                if (!head.inEdges.isEmpty()) {
                    String newHead = popInEdge(head);
                    path.addFirst(newHead);
                    if (!head.hasCapacity()) flows.remove(head);
                    head = nodes.get(headChar(newHead));
                }

                if (!tail.outEdges.isEmpty()) {
                    String newTail = popOutEdge(tail);
                    path.addLast(newTail);
                    if (!tail.hasCapacity()) flows.remove(tail);
                    tail = nodes.get(tailChar(newTail));
                }
            }
        }

        for (int i = 0, n = pathList.size(); i < n; i++) {
            LinkedList<String> pathA = pathList.get(i);
            if (pathA.size() <= 2) break;
            for (int j = i + 1; j < n; j++) {
                LinkedList<String> pathB = pathList.get(j);
                if (pathB.size() <= 2) break;
                cross(pathA, pathB);
            }
        }

        Collections.sort(pathList, new Comparator<List<?>>() {
            public int compare(List<?> o1, List<?> o2) {
                return o1.size() - o2.size(); }});

        for (LinkedList<String> path : pathList) {
            System.out.printf("%d, %s%n", path.size(), path);
        }
    }

    void cross(LinkedList<String> pathA, LinkedList<String> pathB) {
        int ma = -1, mb = -1;
        int ac = pathA.size(), bc = pathB.size();
        int max = Math.max(ac, bc);
        int a = 0;
        for (String aw : pathA) {
            int b = 0;
            for (String bw : pathB) {
                if (tailChar(aw) == headChar(bw)) {
                    int nmax = Math.max(a + (bc - b) + 1, (ac - a) + b - 1);
                    if (max < nmax) {
                        ma = a;
                        mb = b;
                        max = nmax;
                    }
                }
                b++;
            }
            a++;
        }

        if (ma != -1) {
            LinkedList<String> old1 = new LinkedList<String>(pathA);
            LinkedList<String> old2 = new LinkedList<String>(pathB);
            pathA.clear();
            pathB.clear();
            pathA.addAll(old1.subList(0, ma + 1));
            pathA.addAll(old2.subList(mb, bc));
            pathB.addAll(old2.subList(0, mb));
            pathB.addAll(old1.subList(ma + 1, ac));
            cross(pathA, pathB);
        }
    }

    String popInEdge(Node node) {
        int max = -1;
        String next = null;
        for (String s : node.inEdges) {
            Node nextHead = nodes.get(headChar(s));
            if (max < nextHead.flowCapacity()) {
                max = nextHead.flowCapacity();
                next = s;
            }
        }
        node.inEdges.remove(next);
        return next;
    }

    String popOutEdge(Node node) {
        int max = -1;
        String next = null;
        for (String s : node.outEdges) {
            Node nextTail = nodes.get(tailChar(s));
            if (max < nextTail.flowCapacity()) {
                max = nextTail.flowCapacity();
                next = s;
            }
        }
        node.outEdges.remove(next);
        return next;
    }

    static char tailChar(String edge) {
        return toShiritoriChar(edge.charAt(edge.length() - 1));
    }

    static char headChar(String edge) {
        return toShiritoriChar(edge.charAt(0));
    }

    static final String YOUON = "ァィゥェォヵヶッャュョヮ";
    static final String SEION = "アイウエオカケツヤユヨワ";
    static char toShiritoriChar(final char c) {
        if (YOUON.indexOf(c) == -1)
            return c;
        else
            return SEION.charAt(YOUON.indexOf(c));
    }

    static class Node {
        final LinkedList<String> inEdges = new LinkedList<String>();
        final LinkedList<String> outEdges = new LinkedList<String>();
        final Character c;
        int lilmit;

        public Node(Character c) {
            this.c = c;
        }

        void addCominEdge(String e) {
            inEdges.add(e);
        }

        void addGoOutEdge(String e) {
            outEdges.add(e);
        }

        int flowCapacity() {
            return Math.min(inEdges.size(), outEdges.size());
        }

        boolean hasCapacity() {
            return flowCapacity() > 0;
        }
    }
}

<html>
  <head>
    <meta http-equiv="content-type" content="text/html;charset=shift_jis">
    <script type="text/javascript"><!-- //

ls0={};

ls0.wordmap=null;
ls0.counter=null;

ls0.getWordList = function(){
  var str = document.getElementById("ls0_ta").value;
  str = str.replace(/(\t|\r|\n)/g, " ");
  str = str.replace(/ +/g, " ");
  str = str.replace(/ +$/g, "");
  return str.split(" ");
};

ls0.lastChar = function(word){ return word.charAt(word.length-1); };

ls0.chainSort = function(a,b){
  if(!a || !b){ return (!a) ? ( (!b) ? 0 : 1 ) : -1; }
  var a0 = ls0.lastChar(a);
  var b0 = ls0.lastChar(b);
  if(!ls0.counter[a0] || !ls0.counter[b0]){
    return (!ls0.counter[a0]) ? ((!ls0.counter[b0])?0:1) : -1;
  }
  return ls0.counter[b0]-ls0.counter[a0];
};

ls0.execute = function(){
  var result=document.getElementById("ls0_result");
  result.innerHTML="";
  ls0.counter=[];
  ls0.wordmap=[];
  var indexes=[];
  var arr = ls0.getWordList();
  for(var i = 0; i < arr.length; i++){
    var c = arr[i].charAt(0);
    if(!ls0.counter[c]){
      ls0.counter[c]=0;
      ls0.wordmap[c]=[];
      indexes.push(c);
    }
    ls0.counter[c]++;
    ls0.wordmap[c].push(arr[i]);
  }
  for(var i=0;i<indexes.length; i++){
    var c = indexes[i];
    ls0.wordmap[c] = ls0.wordmap[c].sort(ls0.chainSort);
  }
  var pos = Math.floor(Math.random()*arr.length);
  var word = arr[pos];
  arr=null;
  var longest = ls0.getLongest(word);
  for(var i = 0; i < longest.length; i++){
    var div = document.createElement("div");
    div.innerHTML=i+":"+longest[i];
    result.appendChild(div);
  }
};

ls0.getLongest = function(word){
  var longest=[];
  var c0 = word.charAt(0);
  var cz = ls0.lastChar(word);
  ls0.counter[c0]--;
  for(var i = 0;i < ls0.wordmap[c0].length;i++){
    if(!ls0.wordmap[c0][i]){ continue; }
    if(ls0.wordmap[c0][i]!=word){ continue; }
    ls0.wordmap[c0][i]=null;
    break;
  }
  //
  if(ls0.counter[cz]&&ls0.counter[cz]>0){
    ls0.wordmap[cz]=ls0.wordmap[cz].sort(ls0.chainSort);
    for(var i = 0; i < ls0.wordmap[cz].length; i++){
      if(!ls0.wordmap[cz][i]) continue;
      longest = ls0.getLongest(ls0.wordmap[cz][i]);
      break;
    }
  }
  longest.unshift(word);
  return longest;
};

    // --></script>
  </head>
  <body>
    <div>
      <input type="button"
             onclick="javascript:ls0.execute()"
             value="start" />
    </div>
    <div>
      <textarea id="ls0_ta" cols="50" rows="10"></textarea>
    </div>
    <div id="ls0_result"></div>
  </body>
</html>

#define WINVER 0x0400
#define _WIN32_WINDOWS 0
#define _WIN32_WINNT 0
#define _WIN32_IE 0

#define _SECURE_SCL 0
#define _CRT_SECURE_NO_WARNINGS
#define _SCL_SECURE_NO_WARNINGS
#define _CRT_SECURE_CPP_OVERLOAD_STANDARD_NAMES 1

#define WIN32_LEAN_AND_MEAN

#pragma warning(disable: 4512 4819)

#include <iostream>
#include <fstream>
#include <locale>
#include <vector>
#include <deque>
#include <map>
#include <string>
#include <algorithm>
#include <numeric>
#include <iterator>
#include <functional>
#include <memory>
#include <utility>
#include <climits>

#include <omp.h>

#include <boost/timer.hpp>
#include <boost/range.hpp>
#include <boost/iterator_adaptors.hpp>
#include <boost/cast.hpp>

#include <pstade/oven/filtered.hpp>
#include <pstade/oven/algorithm.hpp>
#include <pstade/oven/numeric.hpp>
#include <pstade/oven/indirected.hpp>

#include <windows.h>

using boost::numeric_cast;
namespace ov = pstade::oven;

HANDLE hProcessHeap;
void* operator new(std::size_t size)
{
    if (hProcessHeap == 0)
    {
        hProcessHeap = GetProcessHeap();
    }
    if (void* p = HeapAlloc(hProcessHeap, 0, size))
    {
        return p;
    }
    else
    {
        throw new std::bad_alloc();
    }
}
void* operator new[](std::size_t size)
{
    return operator new(size);
}
void operator delete(void* p)
{
    HeapFree(hProcessHeap, 0, p);
}
void operator delete[](void* p)
{
    operator delete(p);
}

struct WordInfo
{
    std::wstring Word;
    unsigned MaximumLength; //このWordから始めた場合に最も長く続た場合に得られる可能性のある長さ

    explicit WordInfo(const std::wstring& word) : Word(word), MaximumLength(UINT_MAX) {}
    explicit WordInfo(std::wstring&& word) : Word(std::move(word)), MaximumLength(UINT_MAX) {}
    WordInfo(const WordInfo& wi) : Word(wi.Word), MaximumLength(wi.MaximumLength) {}
    WordInfo(WordInfo&& wi) : Word(std::move(wi.Word)), MaximumLength(wi.MaximumLength) {}
    WordInfo& operator =(const WordInfo& wi)
    {
        return *this = WordInfo(wi);
    }
    WordInfo& operator =(WordInfo&& wi)
    {
        Word = std::move(wi.Word);
        MaximumLength = wi.MaximumLength;
        wi.MaximumLength = 0;
        return *this;
    }
};

struct StringFirstComparer : std::binary_function<const WordInfo&, const WordInfo&, bool>
{
    result_type operator ()(first_argument_type lhs, second_argument_type rhs) const
    {
        return (int)lhs.Word[0] < (int)rhs.Word[0];
    }
};

typedef std::vector<WordInfo> wordset_t;

class WordResultList;
typedef std::shared_ptr<WordResultList> wordresult_t;
class WordResultList
{
public:
    static wordresult_t Create(const std::wstring* word, wordresult_t next);
    struct iterator : boost::iterator_adaptor<
        iterator,
        WordResultList*,
        const std::wstring*,
        boost::forward_traversal_tag>
    {
        iterator(WordResultList* p) : iterator_adaptor_(p) {}
        void increment() { base_reference() = base()->next.get(); }
        const std::wstring*& dereference() const { return base_reference()->word; }
    };
    iterator begin(){ return iterator(this); }
    iterator end() { return iterator(NULL); }
    unsigned size() {return listSize;}
private:
    WordResultList(const std::wstring* word, wordresult_t nextWord)
        : word(word), next(std::move(nextWord)), listSize(next.get() ? next->listSize + 1 : 1) {
    }
private: //初めは定義していたが、使わないので削除した。
    WordResultList(const WordResultList& y);
    WordResultList(WordResultList&& y);
    WordResultList& operator =(const WordResultList& y);
    WordResultList& operator =(WordResultList&& y);
private:
    wordresult_t next;
    unsigned listSize;
    const std::wstring* word;
};

wordresult_t WordResultList::Create(const std::wstring* word, wordresult_t next)
{
    __declspec(thread) static HANDLE hHeap; // スレッドごとに異なるヒープを用意
    if (hHeap == 0)
    {
        ULONG flags = 2;
        hHeap = HeapCreate(0, 8192, 0); //HeapDestroyしていません。ごめんなさい。
        HeapSetInformation(hHeap, HeapCompatibilityInformation, &flags, sizeof flags);
    }
    void* raw = HeapAlloc(hHeap, 0, sizeof WordResultList);
    wordresult_t p(new(raw) WordResultList(word, std::move(next)), [](WordResultList* p) {p->~WordResultList();HeapFree(hHeap, 0, p);});
    //wordresult_t p(new WordResultList(word, std::move(next)));
    return p;
}

// 最も長いしりとりの列を返す。
// ただし、これまでの経過をresultList、次に使う言葉をnextWordとする。
wordresult_t GetLongestShifitoriListImpl(
    wordresult_t const& resultList,
    const std::wstring* nextWord,
    const wordset_t& wordSet,
    const wordset_t& stopWordSet)
{
    using namespace std::placeholders;
    wordresult_t result = WordResultList::Create(nextWord, resultList);
    if (resultList && **resultList->begin() == L"セイキハ" && *nextWord == L"ハケヤマ")
    {
        Sleep(0);
    }
    WordInfo lastChar(std::wstring(1, nextWord->back()));
    //nextWordの終わりの文字で始まる言葉を抽出。
    auto r = ov::equal_range(wordSet, lastChar, StringFirstComparer())
        | ov::filtered([&result](WordInfo const& e) -> bool {
            auto it = std::find_if(result->begin(), result->end(), [&e](std::wstring const* p) -> bool {return *p == e.Word;});
            return it == result->end(); // 使用済みの単語を除外
        });
    if (!boost::empty(r))
    {
        // 見つかれば再帰コースへ行く。
        typedef std::pair<wordresult_t, unsigned> result_info_t;
        return std::accumulate(boost::begin(r), boost::end(r), result_info_t(),
            [&](result_info_t && lhs, WordInfo const& e) -> result_info_t
            {
                if (lhs.second >= e.MaximumLength)
                {
                    return lhs; // e.Wordでしりとりを続けても絶対にlhs.firstより長くならない。
                }
                auto rhs = GetLongestShifitoriListImpl(result, &e.Word, wordSet, stopWordSet);
                return (lhs.first ? lhs.first->size() : 0) > rhs->size()
                    ? lhs
                    : result_info_t(std::move(rhs), rhs->size());
            }).first;
    }
    else
    {
        // wordSetから追加できなかった場合、stopWordSetからの追加を試みて終了する。
        auto it = ov::lower_bound(stopWordSet, lastChar, StringFirstComparer());
        if (it != stopWordSet.end() && it->Word[0] == lastChar.Word[0])
        {
            return WordResultList::Create(&it->Word, result);
        }
        else
        {
            return result;
        }
    }
}

std::deque<const std::wstring*> GetLongestShifitoriList(wordset_t& wordSet, const wordset_t& stopWordSet)
{
    std::deque<const std::wstring*> result;
    if (wordSet.empty())
    {
        if (!stopWordSet.empty())
        {
            result.push_back(&stopWordSet.begin()->Word);
        }
        return result;
    }
    else
    {
        // スレッド別に最も長かった結果を保持
        std::vector<std::deque<const std::wstring*>> allResult(omp_get_max_threads());
        const int wordSetSize = numeric_cast<int>(wordSet.size());

#pragma omp parallel for schedule(static)
        for (int i = 0; i < wordSetSize; ++i)
        {
            // 全単語について、その単語から始まるしりとりの列を生成してみる。
            auto r = GetLongestShifitoriListImpl(wordresult_t(), &wordSet[i].Word, wordSet, stopWordSet);
            std::deque<const std::wstring*> t;
            std::copy(r->begin(), r->end(), std::front_inserter(t));
            // wordSet[i].Wordから始めた場合に最も長い(= wordSetとstopWordSetの全単語を使えるとき)列の長さを記憶
            wordSet[i].MaximumLength = numeric_cast<unsigned>(t.size()); //この代入、特にマルチスレッド対策していないけど許して。
            std::deque<const std::wstring*>& cur = allResult[omp_get_thread_num()];
            if (cur.empty() || cur.size() < t.size())
            {
                cur = std::move(t);
            }
        }
        // allResultから最も長いものを選び出して、それを返す。
        return *std::accumulate(allResult.begin(), allResult.end(), static_cast<const std::deque<const std::wstring*>*>(&result),
        [](std::deque<const std::wstring*> const* lhs, std::deque<const std::wstring*> const& rhs) -> const std::deque<const std::wstring*>*
        {
            return lhs->size() > rhs.size() ? lhs : &rhs;
        });
    }
}

namespace
{
    typedef std::pair<wchar_t, wchar_t> dakuon_t;

    const dakuon_t dakuonReplaceList[] =
    {
        dakuon_t(L'ガ', L'カ'), dakuon_t(L'ギ', L'キ'), dakuon_t(L'グ', L'ク'), dakuon_t(L'ゲ', L'ケ'), dakuon_t(L'ゴ', L'コ'),
        dakuon_t(L'ザ', L'サ'), dakuon_t(L'ジ', L'シ'), dakuon_t(L'ズ', L'ス'), dakuon_t(L'ゼ', L'セ'), dakuon_t(L'ゾ', L'ソ'),
        dakuon_t(L'ダ', L'タ'), dakuon_t(L'ヂ', L'チ'), dakuon_t(L'ヅ', L'ツ'), dakuon_t(L'デ', L'テ'), dakuon_t(L'ド', L'ト'),
        dakuon_t(L'バ', L'ハ'), dakuon_t(L'ビ', L'ヒ'), dakuon_t(L'ブ', L'フ'), dakuon_t(L'ベ', L'ヘ'), dakuon_t(L'ボ', L'ホ'),
        dakuon_t(L'パ', L'ハ'), dakuon_t(L'ピ', L'ヒ'), dakuon_t(L'プ', L'フ'), dakuon_t(L'ペ', L'ヘ'), dakuon_t(L'ポ', L'ホ'),
        dakuon_t(L'ァ', L'ア'), dakuon_t(L'ィ', L'イ'), dakuon_t(L'ゥ', L'ウ'), dakuon_t(L'ェ', L'エ'), dakuon_t(L'ォ', L'オ'),
        dakuon_t(L'ャ', L'ヤ'), dakuon_t(L'ュ', L'ユ'), dakuon_t(L'ョ', L'ヨ'), dakuon_t(L'ッ', L'ツ'),
    };
    const std::map<wchar_t, wchar_t> dakuonRepalceMap(boost::begin(dakuonReplaceList), boost::end(dakuonReplaceList));
}
// 濁音・半濁音・拗音を清音に修正
void dakuonReplace(std::wstring& word)
{
    std::for_each(word.begin(), word.end(), [](wchar_t& c)
    {
        auto it = dakuonRepalceMap.find(c);
        if (it != dakuonRepalceMap.end())
        {
            c = it->second;
        }
    });
}

// wordSetのうち、後に続く言葉が全くないものを「ん」で終わる言葉と同様にstopWordSetへ移動させる。
void AdjustStopWord(wordset_t& wordSet, wordset_t& stopWordSet)
{
    auto it = std::remove_if(wordSet.begin(), wordSet.end(),
        [&wordSet, &stopWordSet](const WordInfo& e) -> bool
    {
        //WordInfo lastChar(std::wstring(1, e.Word.back()));
        const wchar_t l = e.Word.back();
        auto pr = [l](WordInfo const& e) -> bool {return e.Word[0] == l;};
        return ov::find_if(wordSet, pr) == wordSet.end()
            && ov::find_if(stopWordSet, pr) == stopWordSet.end();
    });
    wordSet.erase(it, wordSet.end());
    ov::sort(stopWordSet, StringFirstComparer());
}

int main()
{
    std::locale l("");
    std::wcout.imbue(l);
    std::wstring s;
    wordset_t wordSet;
    wordset_t stopWordSet;
    {
        std::wifstream is("h:\\t.txt");
        is.imbue(l);
        while (is >> s)
        {
            dakuonReplace(s);
            if (s[s.length() - 1] == L'ン')
            {
                stopWordSet.push_back(WordInfo(std::move(s)));
            }
            else
            {
                wordSet.push_back(WordInfo(std::move(s)));
            }
        }
    }
    ov::sort(wordSet, StringFirstComparer());
    ov::sort(stopWordSet, StringFirstComparer());
    boost::timer t;
    AdjustStopWord(wordSet, stopWordSet);
    std::wcout << L"start time: " << t.elapsed() << L'\n';
    auto result = GetLongestShifitoriList(wordSet, stopWordSet);
    std::wcout << L"end time: " << t.elapsed() << L'\n';
    std::wcout << L"size: " << result.size() << L'\n';
    ov::copy(result | ov::indirected
        , std::ostream_iterator<std::wstring, wchar_t>(std::wcout, L" "));
    std::wcout << std::endl;
}