Chengdu 2013 Problem G GRE Word Revenge

G.cpp

#include <cassert>
#include <cstdio>
#include <cstring>
#include <set>
#include <string>
#include <queue>
#include <utility>
#include <algorithm>

const int MAX_NODE     = 123456;
const int MAX_BUFFER   = 7654321;
const int BUFFER_LIMIT = 500;

int node_count, trie[MAX_NODE][2], accept[MAX_NODE],
    fail[MAX_NODE], automaton[MAX_NODE][2], match[MAX_NODE];

inline int new_node() {
    int u = node_count ++;
    accept[u] = 0;
    trie[u][0] = trie[u][1] = -1;
    return u;
}

void merge(int &a, int &b) {
    if (b != -1) {
        if (a == -1) {
            a = b;
        } else {
            accept[a] += accept[b];
            for (int t = 0; t < 2; ++ t) {
                merge(trie[a][t], trie[b][t]);
            }
        }
    }
}

void rebuild(int start) {
    std::queue <int> queue;
    for (int t = 0; t < 2; ++ t) {
        if (trie[start][t] == -1) {
            automaton[start][t] = start;
        } else {
            int v = trie[start][t];
            queue.push(v);
            fail[v] = start;
            automaton[start][t] = v;
        }
    }
    match[start] = 0;
    while (!queue.empty()) {
        int u = queue.front();
        queue.pop();
        match[u] = match[fail[u]] + accept[u];
        for (int t = 0; t < 2; ++ t) {
            int v = trie[u][t];
            if (v == -1) {
                automaton[u][t] = automaton[fail[u]][t];
            } else {
                queue.push(v);
                automaton[u][t] = v;
                fail[v] = automaton[fail[u]][t];
            }
        }
    }
}

long long find(int p, const char* buffer) {
    long long ret = 0;
    for (int i = 1; buffer[i]; ++ i) {
        int t = buffer[i] - '0';
        p = automaton[p][t];
        ret += match[p];
    }
    return ret;
}

int main() {
    int test_count;
    scanf("%d", &test_count);
    for (int t = 1; t <= test_count; ++ t) {
        printf("Case #%d:\n", t);
        int q;
        scanf("%d", &q);
        long long last_answer = 0;
        node_count = 0;
        int a_start = new_node();
        int b_start = new_node();
        rebuild(a_start);
        rebuild(b_start);
        int b_size = 0;
        std::set <std::string> patterns;
        while (q --) {
            static char buffer[MAX_BUFFER];
            static char new_buffer[MAX_BUFFER];
            scanf("%s", new_buffer);
            int length = strlen(new_buffer + 1);
            buffer[0] = new_buffer[0];
            buffer[1 + length] = '\0';
            for (int i = 0; i < length; ++ i) {
                buffer[1 + i] = new_buffer[1 + (i + last_answer) % length]; 
            }
            if (*buffer == '+') {
                if (patterns.find(buffer + 1) != patterns.end()) {
                    continue;
                }
                patterns.insert(buffer + 1);
                int p = b_start;
                for (int i = 1; buffer[i]; ++ i) {
                    int t = buffer[i] - '0';
                    if (trie[p][t] == -1) {
                        trie[p][t] = new_node();
                    }
                    p = trie[p][t];
                }
                accept[p] ++;
                b_size += strlen(buffer + 1);
                if (b_size >= BUFFER_LIMIT) {
                    merge(a_start, b_start);
                    trie[b_start][0] = trie[b_start][1] = -1;
                    b_size = 0;
                    rebuild(a_start);
                } 
                rebuild(b_start);
            } else {
                last_answer = find(a_start, buffer) + find(b_start, buffer);
                printf("%lld\n", last_answer);
            }
        }
    }
    return 0;
}