match.cc

#include <iostream>
#include <string>
#include <deque>
#include <array>
using namespace std;

struct Frame
{
    int p;
    int id;
    size_t at;
};

int main()
{
    /*
    const string ids[] = {
        "AABBB",
        "ABCCD",
        "AB",
        "AAB",
        "ABABC",
        "CD"
    };
    */
    const string ids[] = {
        "a",
        "aa",
        "ab",
        "ba"
    };
    const int nids = sizeof(ids)/sizeof(ids[0]);
    //const string str = "ABABCCDAABAABBBAABABCCD";
    //const string str = "ABABCCDAABBBAABAB";
    const string str = "aabaa";

    cout << "ids: { ";
    for (int i = 0; i < nids; ++i) {
        cout << ids[i] << ", ";
    }
    cout << "} " << endl;
    cout << "str: " << str << endl;
    cout << string(20, '-') << endl;

    // !empty(str)
    
    deque<Frame> stack = { { -1, -1, 0 } };
    while (!stack.empty()) {
        const auto& top = stack.back();
        const int p = stack.size() - 1;
        if (top.at < str.size()) {
            int i = 0;
            for (; i < nids; ++i) {
                const auto& head = ids[i];
                if (head != str.substr(top.at, head.size())) continue;
                stack.push_back({ p, i, top.at + head.size() });
            }
            if (p == stack.size() - 1) {
                int p = stack.size() - 1;
                do {
                    int np = stack[p].p;
                    if (p == stack.size() - 1) {
                        stack.pop_back();
                    } else {
                        break;
                    }
                    p = np;
                } while (p > 0);

                if (stack.size() == 1)
                    break;
            }
        } else {
            deque<int> seq;

            int p = stack.size() - 1;
            do {
                int np = stack[p].p;
                seq.push_front(stack[p].id);
                if (p == stack.size() - 1) {
                    stack.pop_back();
                }
                p = np;
            } while (p > 0);

            cout << "seq: " << flush;
            for (size_t i = 0; i < seq.size(); ++i) {
                cout << ids[seq[i]] << ", " << flush;
            }
            cout << endl;

            if (stack.size() == 1)
                break;
        }
    }

    return 0;
}