用c++构造识别符号串的自动机

以下是用C语言构造识别符号串的自动机的示例代码：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_STATES 100
#define MAX_SYMBOLS 256

int transition_table[MAX_STATES][MAX_SYMBOLS];
int fail[MAX_STATES];
int output[MAX_STATES][MAX_STATES];
int state_count = 0;

int get_next_state(char* pattern, int pattern_len, int state, int symbol) {
    if (transition_table[state][symbol] != -1) {
        return transition_table[state][symbol];
    }
    int next_state;
    if (state == 0) {
        next_state = 0;
    } else if (pattern[state] == symbol) {
        next_state = state + 1;
    } else {
        int next_state_fail = fail[state];
        next_state = get_next_state(pattern, pattern_len, next_state_fail, symbol);
    }
    transition_table[state][symbol] = next_state;
    return next_state;
}

void build_automaton(char* patterns[], int pattern_count) {
    memset(transition_table, -1, sizeof(transition_table));
    memset(output, 0, sizeof(output));
    state_count = 1;

    for (int i = 0; i < pattern_count; i++) {
        char* pattern = patterns[i];
        int pattern_len = strlen(pattern);
        int state = 0;
        for (int j = 0; j < pattern_len; j++) {
            int symbol = pattern[j];
            state = get_next_state(pattern, pattern_len, state, symbol);
        }
        output[state][i] = 1;
    }

    for (int i = 0; i < MAX_SYMBOLS; i++) {
        if (transition_table[0][i] == -1) {
            transition_table[0][i] = 0;
        }
    }

    memset(fail, 0, sizeof(fail));
    for (int i = 0; i < MAX_STATES; i++) {
        if (i != 0) {
            fail[i] = transition_table[0][i] == 0 ? 0 : -1;
        }
    }

    int queue[MAX_STATES];
    int front = 0;
    int rear = 0;

    for (int i = 0; i < MAX_SYMBOLS; i++) {
        if (transition_table[0][i] != 0) {
            int nextState = transition_table[0][i];
            fail[nextState] = 0;
            queue[rear++] = nextState;
        }
    }

    while (front < rear) {
        int state = queue[front++];
        for (int i = 0; i < MAX_SYMBOLS; i++) {
            if (transition_table[state][i] != -1) {
                int nextState = transition_table[state][i];
                int failState = fail[state];
                while (transition_table[failState][i] == -1) {
                    failState = fail[failState];
                }
                failState = transition_table[failState][i];
                fail[nextState] = failState;
                for (int j = 0; j < pattern_count; j++) {
                    output[nextState][j] |= output[failState][j];
                }
                queue[rear++] = nextState;
            }
        }
    }

    state_count = rear;
}

void search(char* text, char* patterns[], int pattern_count) {
    int state = 0;
    int text_len = strlen(text);
    for (int i = 0; i < text_len; i++) {
        int symbol = text[i];
        while (transition_table[state][symbol] == -1) {
            state = fail[state];
        }
        state = transition_table[state][symbol];
        for (int j = 0; j < pattern_count; j++) {
            if (output[state][j] == 1) {
                printf("Found pattern %s at position %d\n", patterns[j], i - strlen(patterns[j]) + 1);
            }
        }
    }
}

int main() {
    char* patterns[] = {"ab", "bc", "ca", "abc"};
    int pattern_count = sizeof(patterns) / sizeof(patterns[0]);
    build_automaton(patterns, pattern_count);

    char* text = "abcaabcabc";
    search(text, patterns, pattern_count);

    return 0;
}

该代码使用了AC自动机算法，用于在文本中查找多个模式串。在 `build_automaton()` 函数中，通过循环读取每个模式串，并在自动机中构建相应的状态转移表和输出表。在 `search()` 函数中，使用自动机算法搜索文本中的模式串。在找到模式串时，将其位置打印到控制台上。