#include <iterator>
#include <vector>
#include <iostream>
#include <set>
#include <cassert>

using Transition = std::pair<char, std::string>;

class GrammarHolder {
private:
std::vector<char> non_terminals;
std::vector<char> terminals;
std::vector<Transition> transitions;
char S;
public:
GrammarHolder(std::vector<char> non_terminals,
        std::vector<char> terminals,
        std::vector<Transition> transitions,
        char S) : non_terminals(non_terminals), terminals(terminals), transitions(transitions), S(S) {}

const std::vector<Transition>& getRules() const {
    return transitions;
}
};

class DPParser {
public:
DPParser(const GrammarHolder &g) : g(g) {}

bool Verify(const std::string &s) {
    w = s;

    dynamic_holder.clear();
    dynamic_holder.resize(w.size() + 1);

    dynamic_holder[0].insert(Case(g.getRules()[0], 0, 0));
    size_t current_size;

    do {
        current_size = dynamic_holder[0].size();
        Forecast(0);
        Finish(0);
    } while (dynamic_holder[0].size() != current_size);

    for (size_t i = 1; i <= w.size(); ++i) {
        Peek(i - 1, w[i - 1]);
        do {
            current_size = dynamic_holder[i].size();
            Forecast(i);
            Finish(i);
        } while (dynamic_holder[i].size() != current_size);
    }

    return dynamic_holder[w.size()].find(Case(g.getRules()[0], 1, 0)) != dynamic_holder[w.size()].end();
}
private:
struct Case {
    Transition trans;
    size_t point;
    size_t i;

    Case(Transition rule, size_t point, size_t i) : trans(rule), point(point), i(i) {};

    bool operator<(const Case& another) const {
        if (trans == another.trans) {
            if (point == another.point) {
                return i < another.i;
            }
            return point < another.point;
        }
        return trans < another.trans;
    }
};

std::string w;
std::vector<std::set<Case>> dynamic_holder;
GrammarHolder g;

void Forecast(size_t j) {
    std::vector<Case> new_situations;
    for (std::set<Case>::iterator case_it = dynamic_holder.at(j).begin();
        case_it != dynamic_holder.at(j).end();
        ++case_it
        ) {
        std::vector<Transition> new_rules = g.getRules();
        for (std::vector<Transition>::const_iterator rule = new_rules.begin();
            rule != new_rules.end();
            ++rule) {
            if (rule->first == case_it->trans.second[case_it->point]) {
                new_situations.push_back(Case(*rule, 0, j));
            }
        }
    }

    for (std::vector<Case>::const_iterator situation = new_situations.begin();
         situation != new_situations.end();
         situation++) {
        dynamic_holder[j].insert(*situation);
    }
}

void Peek(size_t j, char x) {
    for (std::set<Case>::iterator situation = dynamic_holder[j].begin();
         situation != dynamic_holder[j].end();
         ++situation) {
        if (situation->trans.second[situation->point] == x) {
            dynamic_holder[j + 1].insert(Case(situation->trans, situation->point + 1, situation->i));
        }
    }
}

void Finish(size_t j) {
    std::vector<Case> new_situations;
    for (std::set<Case>::iterator situation_a = dynamic_holder[j].begin();
         situation_a != dynamic_holder[j].end();
         ++situation_a) {
        if (situation_a->point != situation_a->trans.second.size()) continue;
        for (std::set<Case>::iterator situation_b = dynamic_holder[situation_a->i].begin();
            situation_b != dynamic_holder[situation_a->i].end();
            situation_b++){
            if (situation_b->trans.second[situation_b->point] == situation_a->trans.first) {
                new_situations.push_back(Case(situation_b->trans, situation_b->point + 1, situation_b->i));
            }
        }
    }

    for (std::vector<Case>::iterator situation = new_situations.begin();
         situation != new_situations.end();
         situation++) {
            dynamic_holder[j].insert(*situation);
    }
}
};


int main() {
    std::vector<char> N = {'U', 'S', 'C', 'D'};
    std::vector<char> sigma = {'a', 'b', 'c'};
    std::vector<Transition> P = {
            {'U', "S"},
            {'S', "C"},
            {'D', "aDb"},
            {'S', "SC"},
            {'C', "cD"},
            {'D', ""},
    };
    char S = 'U';

    GrammarHolder grammar = GrammarHolder(N, sigma, P, S);


    DPParser dp_pars(grammar);


    std::string good_sample = "caaabbbcabcabcc";
    assert(dp_pars.Verify(good_sample));
    std::cout << "good sample successfully verified\n";

    std::string bad_sample = "aaabbbcabcabcc";
    assert(dp_pars.Verify(good_sample));
    std::cout << "bad sample successfully verified\n";
    return 0;
}