首页 > 代码库 > 后缀自动机 && 题目

后缀自动机 && 题目

2024-11-15 09:46:40   203人阅读

 

因为明天要讲解后缀自动机了，所以只能抱抱佛脚，临时做做题目。其实很久以前看过，但是不太懂，看的是clj的原文，不太懂。现在只能临时看看是怎么弄的，应付下。

 

---------------------------------------------------------------------------------------------------------------------------------------------------------------

1、自动机A为后缀自动机，A(sub) = true当且仅当sub是str的后缀。

2、一个较差的和后缀自动机有相同功能的东西是trie，把所有后缀都insert进去trie里面，但是空间&&时间复杂度O（N^2），不行。

3、有一个空间和时间复杂度都是O(N)的，就是：以ACADD为例子

技术分享

也就是向每个字符都添加一条边，然后顺着这条边遍历，就能找到所有后缀。也能保存所有子串。

但是查找复杂度O（N^2）

注意到连接去字符‘A‘的边是有两条的，也就是这个图只能用邻接表来存，不能像trie这样用pNext[26]这样存，所以查找是O(N^2)

 

后缀自动机是一个基于trie的字符串有向图，时间和空间复杂度均为O（N）

构造过程：

假设现在已经建立好前t个字符的后缀自动机，现在要增加一个字符x，使得其变成tx的后缀自动机。

struct Node {
    int cnt, id, pos; // cnt表示在后缀自动机中从root走到它最多需要多少步
    //id表示它是第几个后缀自动机节点，指向了它，但是不知道是第几个，需要id判断
    //pos表示它在原串中的位置。
    struct Node *pNext[N], *fa;
}suffixAutomaon[maxn * 2], *root, *last; //大小需要开2倍，因为有一些虚拟节点
int t; // 用到第几个节点
struct Node *create(int cnt = -1, struct Node *node = NULL) { //新的节点
    if (cnt != -1) {
        suffixAutomaon[t].cnt = cnt, suffixAutomaon[t].fa = NULL;
        suffixAutomaon[t].id = t;
        for (int i = 0; i < N; ++i) suffixAutomaon[t].pNext[i] = NULL;
    } else {
        suffixAutomaon[t] = *node; //保留了node节点指向的信息
        suffixAutomaon[t].id = t; //必须要有的，不然id错误
    }
    return &suffixAutomaon[t++];
}
void init() {
    t = 0;
    root = last = create(0, NULL);
}
void addChar(int x, int pos) { //pos表示在原串的位置
    struct Node *p = last, *np = create(p->cnt + 1, NULL);
    np->pos = pos, last = np; //最后一个可接收后缀字符的点。
    for (; p != NULL && p->pNext[x] == NULL; p = p->fa) p->pNext[x] = np;
    if (p == NULL) {
        np->fa = root;
        return;
    }
    struct Node *q = p->pNext[x];
    if (q->cnt == p->cnt + 1) { //中间没有任何字符
        np->fa = q;
        return;
    }
    struct Node *nq = create(-1, q); // 新的q节点，用来代替q，帮助np接收后缀字符
    nq->cnt = p->cnt + 1; //就是需要这样，这样中间不包含任何字符
    q->fa = nq, np->fa = nq; //现在nq是包含了本来q的所有指向信息
    for (; p && p->pNext[x] == q; p = p->fa) {
        p->pNext[x] = nq;
    }
}
void build(char str[], int lenstr) {
    init();
    for (int i = 1; i <= lenstr; ++i) addChar(str[i] - ‘a‘, i);
}

 

后缀自动机 && 题目


联系
我们