DouKaku?

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