#include <iostream>
#include <string>
#include <vector>
#include <iterator>
#include <set>
 
using namespace std;
 
bool IsIncantation(string const& sentence, set<string> magicDic)
{
    size_t n = sentence.size();
    if (n == 0)
        return false;
 
    vector<bool> incanBits(n);
    incanBits&#91;0] =
        ( magicDic.find(sentence.substr(0, 1)) != magicDic.end() );
 
    for (size_t i = 1; i < n; ++i)
    {
        if ( (magicDic.find(sentence.substr(0, i + 1)) != magicDic.end()) )
        {
            incanBits&#91;i] = true;
            continue;
        }
 
        incanBits&#91;i] = false;
        for (size_t j = 0; j < i; ++j)
        {
            if (incanBits&#91;j] == true &&
                magicDic.find(sentence.substr(j + 1, i - j)) != magicDic.end())
            {
                incanBits&#91;i] = true;
                break;
            }
        }
    }
 
    //copy(incanBits.begin(), incanBits.end(), ostream_iterator<bool>(cout, " "));
    return incanBits&#91;n - 1];
}
 
int main()
{
    string incants&#91;] = { "Zeta", "Mo", "Ma", "Doc", "EEEEEE", "Ear" };
    set<string> dic;
    for (size_t i = 0; i < sizeof(incants)/sizeof(incants&#91;0]); ++i)
        dic.insert(incants&#91;i]);
 
    string sentence("MoMaMaMaDocEarEEEEEEZetaMoMo");
    bool isIncant = IsIncantation(sentence, dic);
 
    cout << "The sentence \"" << sentence << "\" " << (isIncant ? "is " : "is not ")
        << "an incantation" << endl;
 
    system("pause");
}