Temporary

aho_corasick_demo_2.cpp

#include <set>
#include <map>
#include <list>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <cassert>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <unordered_set>

using namespace std;

#define FOR(i, L, U) for(int i=(int)L; i<=(int)U; i++)
#define FORD(i, U, L) for(int i=(int)U; i>=(int)L; i--)

#define READ(x) freopen(x, "r", stdin)
#define WRITE(x) freopen(x, "w", stdout)

#define ff first
#define ss second
#define PQ priority_queue
#define PB push_back
#define SZ size()

#define EPS 		1e-9
#define SQR(x) 		((x)*(x))
#define INF 		2000000000
#define TO_DEG 		57.29577951
#define PI 			2*acos(0.0)

#define ALL_BITS					((1 << 31) - 1)
#define NEG_BITS(mask)				(mask ^= ALL_BITS)
#define TEST_BIT(mask, i)			(mask & (1 << i))
#define ON_BIT(mask, i)				(mask |= (1 << i))
#define OFF_BIT(mask, i)			(mask &= NEG_BITS(1 << i))
#define IS_POWER_TWO(x)				(x && !(x & (x-1)))
#define OFF_RIGHTMOST_SET_BIT(x)	(x & (x-1))

typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
typedef pair<uint, uint> PUU;
typedef pair<double, double> PDD;
typedef vector<bool> VB;
typedef vector<int> VI;
typedef vector<uint> VU;
typedef vector<double> VD;
typedef vector<char> VC;
typedef vector<string> VS;
typedef map<int, int> MII;
typedef map<char, int> MCI;
typedef map<string, int> MSI;
typedef vector<vector<bool> > VVB;
typedef vector<vector<int> > VVI;
typedef vector<vector<double> > VVD;
typedef vector<vector<PII> > VVPII;

ULL GCD(ULL a, ULL b) { while (b)b ^= a ^= b ^= a %= b;  return a; }

// UP, RIGHT, DOWN, LEFT, UPPER-RIGHT, LOWER-RIGHT, LOWER-LEFT, UPPER-LEFT
int dx[8] = { -1, 0, 1, 0, -1, 1,  1, -1 };
int dy[8] = { 0, 1, 0,-1,  1, 1, -1, -1 };

// Represents all moves of a knight in a chessboard
int dxKnightMove[8] = { -1, -2, -2, -1,  1,  2, 2, 1 };
int dyKnightMove[8] = {  2,  1, -1, -2, -2, -1, 1, 2 };

inline int srcInt() { int ret; scanf("%d", &ret); return ret; }
inline int srcUInt() { uint ret; scanf("%u", &ret); return ret; }

#define WHITE 0
#define GRAY 1
#define BLACK 2

#define MAX 100000
#define MAXS 500
#define MAXC 26

struct TrieNode {
    int parent;
    map<char, int> children;
    bool isKey;
    int failNode;
    unordered_set<int> matches;

    TrieNode() : parent(-1), isKey(false), failNode(0) {}
    TrieNode(int p) : parent(p), isKey(false), failNode(0) {}
};
vector<TrieNode> trie(1);

int charValue(char ch) {
    return ch - 'a';
}

void insert(string const& key, int wordId) {
    int node = 0;
    for (int i = 0; i < key.length(); ++i) {
        int ch = charValue(key[i]);
        int &nextNode = trie[node].children[ch];
        if (nextNode == 0) {
            nextNode = trie.size();
            trie.push_back(TrieNode(node));
        }
        node = nextNode;
    }
    trie[node].matches.insert(wordId);
}

void bfs() {
    trie[0].failNode = 0;

    queue<int> Q;
    Q.push(0);
    while (!Q.empty()) {
        int u = Q.front(); Q.pop();

        map<char, int>::iterator it = trie[u].children.begin();
        while (it != trie[u].children.end()) {
            int ch = charValue(it->first);
            int v = it->second;

            int failNode = trie[u].failNode;
            while (failNode && !trie[failNode].children.count(ch))
                failNode = trie[failNode].failNode;
            failNode = trie[failNode].children[ch];

            trie[v].failNode = failNode;
            trie[v].matches.insert(trie[failNode].matches.begin(), trie[failNode].matches.end());

            it++;
        }
    }
}

void searchWords(string const& str) {
    int node = 0;
    for (int i = 0; i < str.length(); ++i) {

    }
}

int main()
{
    //READ("input.txt");
    //WRITE("input.txt");

    int i, j;
    int TC, tc;
    double cl = clock();

    vector<string> keys;
    keys.PB("he");
    keys.PB("she");
    keys.PB("his");
    keys.PB("hers");
    string text = "ashishers";

    searchWords(keys, text);

    cl = clock() - cl;
    fprintf(stderr, "Total Execution Time = %lf seconds\n", cl / CLOCKS_PER_SEC);

    return 0;
}