maritalk-bot/markov.cpp

#include <iostream>
#include <vector>
#include <map>
#include <deque>
#include <string>
#include <random>
#include <ctime>

using namespace std;
using prefix = deque<string>;

constexpr int NPREF  = 2;
constexpr int MAXGEN = 10000;
const  string NOWORD = "\n";

static map<prefix, vector<string>> statetab;

void add(prefix& p, const string& s)
{
    if (p.size() == NPREF) {
        statetab[p].emplace_back(s);
        p.pop_front();
    }
    p.emplace_back(s);
}

void build(prefix& p, istream& in)
{
    string buf;

    while (in >> buf)
        add(p, buf);
}

void generate(const int nwords)
{
    prefix p;
    int i;

    mt19937_64 rng;
    rng.seed(unsigned(time(nullptr)));

    for (i = 0; i < NPREF; ++i)
        add(p, NOWORD);

    for (i = 0; i < nwords; ++i) {
        const vector<string>& suf = statetab[p];
        const string& w = suf[rng() % suf.size()];

        if (w == NOWORD)
            break;
        cout << w << "\n";
        p.pop_front();
        p.emplace_back(w);
    }
}

int
main(int argc, char *argv[])
{
    constexpr int nwords = MAXGEN;
    prefix current;

    for (int i = 0; i < NPREF; ++i)
        add(current, NOWORD);

    build(current, cin);
    add(current, NOWORD);
    generate(nwords);

    return 0;
}