Aho-Corasick

#include <iostream>
#include <queue>
#include <cstring>
#include <string>
#include <vector>
using namespace std;

vector<string> words;
int state = 0;
int g[1<<17][26];
int green[1<<17];
int blue[1<<17];
vector<int> fin[1<<17];


void BuildMachine()
{
    memset(g,-1,sizeof(g));
    memset(blue,-1,sizeof(blue));
    memset(green,-1,sizeof(green));

    string currentWord;
    int currentState;
    int c;
    //make trie
    state = 1;
    for(int i=0; i<words.size(); i++)
    {
        currentState = 0;
        currentWord = words[i];
        //cout << "At word "  << i << endl;
        for(int j=0; j<currentWord.size(); j++)
        {
            c = currentWord[j] - 'a';
            //cout << "      "  << currentState << ' ' << g[currentState][c] << ' ' << state << endl;
            if(g[currentState][c] == -1) {
                g[currentState][c] = state++;
            }
            currentState = g[currentState][c];
        }
        fin[currentState].push_back(i);
    }

    //cout << state << endl;

    queue<int> q;

    for(int i=0; i<26; i++){
        if(g[0][i] == -1){
            g[0][i] = 0;
        }
        if(g[0][i] != -1 && g[0][i] != 0)
        {
            blue[g[0][i]]  = 0;
            q.push(g[0][i]);
        }
    }

    //make sufix arcs
    vector<int> greens;
    int current;
    int blueArc;
    while(!q.empty())
    {
        current = q.front(); q.pop();
        for(int i=0; i<26; i++)
        {
            greens.clear();
            if(g[current][i] != -1) {
                blueArc = blue[current];
                while(g[blueArc][i] == -1) blueArc = blue[blueArc];

                blueArc = g[blueArc][i];
                blue[g[current][i]] = blueArc;
                q.push(g[current][i]);

                //cout << current << '-'  << g[current][i] << ' '  << blueArc << endl;

                while(fin[blueArc].size() == 0){
                    greens.push_back(blueArc);
                    blueArc = blue[blueArc];
                    if(blueArc  == 0) break;
                }
                if(blueArc == 0) continue;
                green[g[current][i]] = blueArc;
                for(int j=0; j<greens.size(); j++) green[greens[j]] = blueArc;
            }
        }
    }
}

int nextState(int current, char input)
{
    int c = input - 'a';
    //cout << c << '-' << g[current][c] << endl;
    if(g[current][c] != -1) return g[current][c];

    int blueArc = blue[current];
    while(g[blueArc][c] == -1) blueArc = blue[blueArc];

    return g[blueArc][c];
}

struct match
{
    int pos;
    int id;

    match(){}

    match(int a, int b)
    {
        id = a;
        pos = b;
    }
};

vector<match> output;



int main()
{
    int n;
    cout << "Enter number of words: ";
    cin >> n;

    cout << "Enter words:\n";

    string s;
    for(int i=0; i<n; i++) {
        cin >> s;
        words.push_back(s);
    }

    BuildMachine();

    cout << "Enter input text: \n";
    cin >> s;
    int m = s.size();

    int currentState = 0;
    int cs = 0;
    for(int i=0; i<m; i++)
    {
        cs = nextState(cs,s[i]);
        //cout << "At pos: "  << i << ' ' << " State: " << currentState << endl;
        currentState = cs;
        while(currentState != -1)
        {
            for(int j=0; j<fin[currentState].size(); j++)
                output.push_back(match(fin[currentState][j],i));
            currentState = green[currentState];
        }
    }

    //cout << "Entered\n";
    cout << "Found " << output.size() << " matches!\n";

    for(int i=0; i<output.size(); i++)
    {
        cout << words[output[i].id] << " at end position "  << output[i].pos << endl;
    }

    return 0;
}