#include <iostream>
#include <set>
#include <map>
#include <string>
#include <vector>

using namespace std;

vector<vector<string> > _segmentString(const string& inputString, set<string>& wordList, map<string, vector<vector<string> > >& cacheMap) {
    auto targetCache = cacheMap.find(inputString);
    if (targetCache != cacheMap.end()) {
        return targetCache->second;
    }
    auto retVector = vector<vector<string> >();

    if (inputString.size() <= 1) {
        auto vec = vector<string>();
        vec.push_back(inputString);
        retVector.push_back(vec);
    } else {
        for (int i = 1; i <= inputString.size(); i++) {
            auto frontSubString = inputString.substr(0, i);
            if (wordList.find(frontSubString) != wordList.end()) {
                auto backSubString = inputString.substr(i, inputString.size());
                if (backSubString.size()) {
                    auto backSegments = _segmentString(backSubString, wordList, cacheMap);
                    for (auto iter = backSegments.begin(); iter != backSegments.end(); ++iter) {
                        auto vec = vector<string>(*iter);
                        vec.insert(vec.begin(), frontSubString);
                        retVector.push_back(vec);
                    }
                } else {
                    auto vec = vector<string>();
                    vec.push_back(frontSubString);
                    retVector.push_back(vec);
                }
            }
        }
    }
    cacheMap.insert(pair<string, vector<vector<string> > >(inputString, retVector));

    return retVector;
}

vector<vector<string> > segmentString(const string& inputString, set<string>& wordList) {
    auto cacheMap = map<string, vector<vector<string> > >();
    return _segmentString(inputString,  wordList, cacheMap);
}

int main() {
    string aaa = "nimenhao";
    //nimenhao
    auto wordlist = set<string>();
    for (char c = 'a'; c <= 'z'; ++c) {
        wordlist.insert(string(1, c));
    }
    string l[] = {"ni", "me", "men", "ha", "hao", "ao"};
    for (auto i = 0; i < sizeof(l) / sizeof(string); i++) {
        wordlist.insert(l[i]);
    }
    auto segResult = segmentString(aaa, wordlist);
    for (auto iter = segResult.begin(); iter != segResult.end(); ++iter) {
        auto& row = *iter;
        for (auto innerIter = row.begin(); innerIter != row.end(); ++innerIter) {
            if (innerIter != row.begin()) {
                cout << '|';
            }
            cout << '(' << *innerIter << ')';
        }

        cout << endl;
    }

    return 0;
}

/*
 *
 * Result Will Be
(n)|(i)|(m)|(e)|(n)|(h)|(a)|(o)
(n)|(i)|(m)|(e)|(n)|(h)|(ao)
(n)|(i)|(m)|(e)|(n)|(ha)|(o)
(n)|(i)|(m)|(e)|(n)|(hao)
(n)|(i)|(me)|(n)|(h)|(a)|(o)
(n)|(i)|(me)|(n)|(h)|(ao)
(n)|(i)|(me)|(n)|(ha)|(o)
(n)|(i)|(me)|(n)|(hao)
(n)|(i)|(men)|(h)|(a)|(o)
(n)|(i)|(men)|(h)|(ao)
(n)|(i)|(men)|(ha)|(o)
(n)|(i)|(men)|(hao)
(ni)|(m)|(e)|(n)|(h)|(a)|(o)
(ni)|(m)|(e)|(n)|(h)|(ao)
(ni)|(m)|(e)|(n)|(ha)|(o)
(ni)|(m)|(e)|(n)|(hao)
(ni)|(me)|(n)|(h)|(a)|(o)
(ni)|(me)|(n)|(h)|(ao)
(ni)|(me)|(n)|(ha)|(o)
(ni)|(me)|(n)|(hao)
(ni)|(men)|(h)|(a)|(o)
(ni)|(men)|(h)|(ao)
(ni)|(men)|(ha)|(o)
(ni)|(men)|(hao)
 *
 * */