AC automaton implement in C++

acauto_compact.cpp

#include<iostream>
#include<sstream>
#include<string>
#include<queue>
#include<cstdio>
#include<cstring>
#include<cctype>
#include<vector>
#include<cstring>
#include<algorithm>
#include<vector>
#define For(i, n) for(i = 0; i < n; i++)
#define Forr(i, l, n) for(i = l; i < n; i++)
typedef long long LL;
using namespace std;
const int N = 1002;
const char SEP = '$';
const int D[8][2] = {{-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}, {-1, -1}};

// AC automaton code /////////////////////////////////////////////////////////
// Usage: 
//   *) start_build()
//   *) add_string(s1, n1)
//   *) add_string(s2, n2)
//   ...
//   *) end_build()
// 

const int E = 26;
struct ACNode{
    int nexts[E];
    int out;
    int fail;

    ACNode():out(0){};
};

ACNode nodes[100000];

class ACAuto{
    public:
        int ncnt;
        int st0;
        int aux;

        inline int char2code(char c){ return c - 'a'; }

        inline char code2char(int code){ return 'a' + code; }

        int new_node(){
            int i;
            For(i, E) nodes[ncnt].nexts[i] = -1;
            nodes[ncnt].fail = -1;
            nodes[ncnt].out = 0;
            return ncnt++;
        }

        inline int set_transition(int s, char c, int s1){
            nodes[s].nexts[char2code(c)] = s1;
        }

        inline int get_transition(int s, char c){
            return nodes[s].nexts[char2code(c)];
        }

        void start_build(){
            int i;
            ncnt = 0;
            aux = new_node();
            st0 = new_node();
            For(i, E) nodes[aux].nexts[i] = st0;
            nodes[st0].fail = aux;
        }

        void add_string(const char*s, int n){
            int st1, st2;
            int i;
            char c;
            st1 = st0;
            For(i, n){
                c = s[i];
                st2 = get_transition(st1, c);
                if(st2 == -1){
                    st2 = new_node();
                    set_transition(st1, c, st2);
                }
                st1 = st2;
            }
            // the end of the word s
            nodes[st1].out += 1;
        }

        int get_through(int s, char c){
            int s1, s0;
            s0 = s;
            while(1){
                s1 = get_transition(s, c);
                if(s1 != -1){
#ifndef DEBUG
                    //lazy 
                    set_transition(s0, c, s1);
#endif
                    return s1;
                }else s = nodes[s].fail;
            }
        }

        void end_build(){
            queue<int> que;
            int st1, st2, st3;
            char c, ci;

            que.push(st0);
            while(!que.empty()){
                st1 = que.front();
                que.pop();
                For(ci, E){
                    c = code2char(ci);
                    st2 = get_transition(st1, c);
                    if(st2 != -1){
                        que.push(st2);
                        st3 = get_through(nodes[st1].fail, c);
                        nodes[st2].fail = st3;
                        // union end of words that recognized by st2
                        // nodes[st2].out += nodes[st3].out;
                    }
                }
            }
        }

#ifdef DEBUG
        void print_tire(char c = '^', int st = -2, int indent = 0){
            if(st == -2) st = st0;
            else if(st == -1) return;
            int j;
            For(j, indent) cout << ' ';
            string s; stringstream ss;
            printf("(%c) st:[%d] out:[%d] fail:{%d}\n", c, st, nodes[st].out, nodes[st].fail);
            For(j, E){
                c = code2char(j);
                print_tire(c, get_transition(st, c), indent+4);
            }
        }
#endif
};
/////////////////// end of AC automaton code //////////////////////////////////////////
ACAuto ac;
int main(){
    int n, i;
    string s;
    cin >> n;
    ac.start_build();
    For(i, n){
        cin >> s;
        ac.add_string(s.c_str(), s.size());
    }
    ac.end_build();
    ac.print_tire();
}