[数据结构与算法][高级数据结构] 6. ac自动机

ac自动机

1. 所有点的失败指针一定在它的上层
2. 很像广搜
3. 构建复杂度O(len * k)，匹配复杂度O(n)，是一个很复杂的东西

#include <cstdio>
#include <cstring>
#include <sstream>
#include <ctime>

#define base 26

typedef struct Node {
    const char *str; // 存字符串
    struct Node *next[base], *fail;
} Node;

typedef struct Queue {
    Node **data; // **
    int head, tail;
} Queue;

/* queue */
Queue *initQueue(int n) {
    Queue *q = (Queue *)malloc(sizeof(Queue));
    q->data = (Node **)malloc(sizeof(Node *) * n);
    q->head = q->tail = 0;
    return q;
}

int empty(Queue *q) {
    return q->head == q->tail;
}

Node *front(Queue *q) {
    return q->data[q->head];
}

void push(Queue *q, Node *node) {
    q->data[q->tail++] = node;
    return ;
}

void pop(Queue *q) {
    if (empty(q)) return ;
    q->head++;
    return ;
}

void clearQueue(Queue *q) {
    if (q == NULL) return ;
    free(q->data);
    free(q);
    return ;
}

/* 字典树 */
int node_cnt = 0;
Node *getNewNode() {
    Node *p = (Node *)malloc(sizeof(Node));
    p->str = NULL;
    p->fail = NULL;
    node_cnt++;
    memset(p->next, 0, sizeof(Node *) * base);
    return p;
}

void clear(Node *root) {
    if (root == NULL) return ;
    for (int i = 0; i < base; i++) {
        clear(root->next[i]);
    }
    if (root->str) free((char *)root->str);
    free(root);
    return ;
}

const char *copyStr(const char *s) {
    int n = strlen(s);
    char *buff = (char *)malloc(n + 1);
    strcpy(buff, s);
    return buff;
}

void insert(Node *root, const char *s) {
    Node *p = root;
    for (int i = 0; s[i]; i++) {
        if (p->next[s[i] - 'a'] == NULL) {
            p->next[s[i] - 'a'] = getNewNode();
        }
        p = p->next[s[i] - 'a'];
    }
    p->str = copyStr(s); // str -> flag
    return ;
}

/* fail创建 ac自动机匹配 */

void initBuildFailQueue(Node *root, Queue *q) {
    root->fail = NULL;
    for (int i = 0; i < base; i++) {
        if (root->next[i] == NULL) continue;
        root->next[i]->fail = root;
        push(q, root->next[i]);
    }
    return ;
}

void build_fail(Node *root) {
    Queue *q = initQueue(node_cnt);
    initBuildFailQueue(root, q);
    while (!empty(q)) {
        Node *p = front(q);
        for (int i = 0; i < base; i++) {
            if (p->next[i] == NULL) continue;
            Node *k = p->fail;
            // 当前节点的父节点的失败指针是空节点，继续往上找
            while (k != root && root->next[i] == NULL) {
                k = k->fail;
            }
            if (k->next[i] != NULL) k = k->next[i];
            p->next[i]->fail = k;
            push(q, p->next[i]);
        }
        pop(q);
    }
    clearQueue(q);
    return ;
}

void match_ac(Node *root, const char *s) {
    Node *p = root, *q;
    for (int i = 0; s[i]; i++) { // 遍历s
        while (p != root && p->next[s[i] - 'a'] == NULL) {
            p = p->fail;
        }
        if (p->next[s[i] - 'a']) p = p->next[s[i] - 'a'];
        q = p;
        while (q) {
            if (q->str != NULL) printf("find %s\n", q->str);
            q = q->fail;
        }
    }
    return ;
}

int main() {
    int n;
    char s[100];
    Node *root = getNewNode();
    
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%s", s);
        insert(root, s);
    }
    build_fail(root);
    
    scanf("%s", s);
    match_ac(root, s);

    return 0;
}