AC自动机及多模式匹配

  • 在接触AC自动机之前,只仅仅掌握单模式匹配的算法:比如KMP、BMH等算法;经过优化后,KMP和BMH都具有线性时间复杂度,而实际情况下,一般的匹配问题BMH具有亚线性的表现。而昨天接触的AC自动机则是一种结合了字典树和KMP的一种算法,使得在多模式匹配下,时间复杂度达到$O(Σmi + n)$,其中n为原串长度,mi为第i个模式串的长度;
  • 匹配过程中类似于KMP,原串不走回头路,利用之前已经匹配过的结果来构造特殊的字典树从而形成AC自动机;
  • 创建自动机的过程中,最为重要的是fail指针的构造;我是从这篇文章中学会的,AC自动机算法详解;fail指针的作用类似于KMP中的next数组;
  • 我的这个模板中并没有考虑对自动机的优化, 比如ptr->fail->next[i]ptr->next[i]若同时不存在, 则ptr->fail其实是可以直接指向ptr->fail->fail的原因很简单, 因为ptr->next[i]发生失配时, ptr = ptr->fail, 此时肯定仍然失配, 需要继续ptr->fail,当然优化的代价是增加对存储空间的占用, fail需要变为vector<trieTreeNode*> fail,每个字母都应对应一个fail指针。
1
////////////////////////////////////////////////////////////////////////////////
2
/*
3
1 const vector<string> &patterns: several pattern strings;
4
2 const string &s: original strings;
5
3 vector<string> &answer: the patterns which are matched in the original strings;
6
4 return the number of patterns which are matched.
7
*/
8
////////////////////////////////////////////////////////////////////////////////
9
#include <iostream>
10
#include <vector>
11
#include <queue>
12
#include <string>
13
#include <unordered_set>
14
#define ALPH_NUM 26
15
using namespace std;
16
17
struct trieTreeNode {
18
    vector<trieTreeNode*> next;
19
    bool mark;
20
    trieTreeNode *fail;
21
    trieTreeNode(): next(26, nullptr), mark(false), fail(nullptr) {}
22
};
23
24
trieTreeNode *createAcAutomation(const vector<string> &patterns);
25
int findPatterns(vector<string> &answer, trieTreeNode *root, const string &s);
26
void makeFoundPatterns(vector<string> &answer, unordered_set<trieTreeNode*> &save, trieTreeNode *root, string pattern);
27
inline char turn_char(int index);
28
int multiPatternsMatchingByAcAutomation(const vector<string> &patterns, const string &s, vector<string> &answer);
29
30
trieTreeNode *createAcAutomation(const vector<string> &patterns) {
31
    trieTreeNode *root = new trieTreeNode(), *ptr, *cur;
32
    for (int i = 0; i != patterns.size(); ++i) {
33
        cur = root;
34
        for (int k = 0; k != patterns[i].size(); ++k) {
35
            int index = patterns[i][k] - 'a';
36
            if (!cur->next[index])
37
                cur->next[index] = new trieTreeNode();
38
            cur = cur->next[index];
39
        }
40
        cur->mark = true;
41
    }
42
    queue<trieTreeNode*> makeFail;
43
    makeFail.push(root);
44
    while (!makeFail.empty()) {
45
        cur = makeFail.front(); makeFail.pop();
46
        for (int i = 0; i != ALPH_NUM; ++i) {
47
            if (cur->next[i]) {
48
                for (ptr = cur->fail; ptr && !ptr->next[i]; ptr = ptr->fail);
49
                cur->next[i]->fail = ptr ? ptr->next[i] : root;
50
                makeFail.push(cur->next[i]);
51
            }
52
        }
53
    }
54
    return root;
55
}
56
57
int findPatterns(vector<string> &answer, trieTreeNode *root, const string &s) {
58
    int count = 0;
59
    string pattern;
60
    unordered_set<trieTreeNode*> save;
61
    trieTreeNode *cur = root;
62
    for (int i = 0; i != s.size(); ) {
63
        int index = s[i] - 'a';
64
        if (!cur) {
65
            cur = root; ++i;
66
        }
67
        else if (cur->next[index]) {
68
            cur = cur->next[index];
69
            if (cur->mark) {
70
                ++count;
71
                save.insert(cur);
72
            }
73
            ++i;
74
        }
75
        else {
76
            cur = cur->fail;
77
            if (cur && cur->mark) {
78
                ++count;
79
                save.insert(cur);
80
            }
81
        }
82
    }
83
    makeFoundPatterns(answer, save, root, pattern);
84
    return count;
85
}
86
87
void makeFoundPatterns(vector<string> &answer, unordered_set<trieTreeNode*> &save,
88
    trieTreeNode *root, string pattern) {
89
    unordered_set<trieTreeNode*>::iterator it = save.find(root);
90
    if (it != save.end())
91
        answer.push_back(pattern);
92
    for (int i = 0; i != ALPH_NUM; ++i) {
93
        if (root->next[i]) {
94
            string t(pattern);
95
            t.push_back(turn_char(i));
96
            makeFoundPatterns(answer, save, root->next[i], t);
97
        }
98
    }
99
}
100
101
inline char turn_char(int index) {
102
    return 'a' + index;
103
}
104
105
int multiPatternsMatchingByAcAutomation(const vector<string> &patterns, const string &s, vector<string> &answer) {
106
    trieTreeNode *root = createAcAutomation(patterns);
107
    return findPatterns(answer, root, s);
108
}

二叉树与森林的转换

思路

  • 利用递归建立节点完成转换。首先我们观察二叉树的结构,包含第一个孩子,及其兄弟。关键在于:那么我们在构造递归时,每层recursion中都必须找到对应sibling和firstchild。对于双亲表示法,我们很难找到孩子,对于孩子表示法,我们很难找到双亲(因为找到双亲是找到本节点兄弟的唯一方法,或在传参时也传入父节点指针)。
  • 不同形式间转换的技巧。对于要被转换的结构,需要传入针对它单次recursion完成结构内部所有成员构造对应的转换的结构的信息。就能完成一层递归。同时应注意递归结束的条件。

孩子表示法生成二叉树算法

1
typedef struct BiTree{
2
    ElemType data;
3
    struct BiTree *firstchild, *sibling;
4
}BTnode, *BTree;
5
6
typedef struct Lnode{
7
    int child;
8
    struct Lnode *next;
9
}Lnode, *CList;
10
typedef struct Cbox{
11
    ElemType data;
12
    CList firstchild;
13
}Cbox, *Cnode;
14
typedef struct CTnode{
15
    Cnode node;
16
    int n, r;
17
}CTree;
18
19
void TransformChildTreeToBinaryTree(CTree CT, BTree &BT, int preroot, int root){
20
    if (root == -1){
21
        BT = NULL; return;
22
    }
23
    BT = (BTree)malloc(sizeof(BTnode));
24
    BT->data = CT.node[root].data;
25
    int rsave;
26
    if (CT.node[root].firstchild){
27
        rsave = CT.node[root].firstchild->child;
28
    }
29
    else{
30
        rsave = -1;
31
    }
32
    TransformChildTreeToBinaryTree(CT, BT->firstchild, root, rsave);
33
    if (preroot == -1){
34
        BT->sibling = NULL; return;
35
    }
36
    CList p = CT.node[preroot].firstchild;
37
    while (p && p->data != root){
38
        p = p->next;
39
    }
40
    if (p->next){
41
        rsave = p->next->child;
42
    }
43
    else{
44
        rsave = -1;
45
    }
46
    TransformChildTreeToBinaryTree(CT, BT->sibling, preroot, rsave);
47
    return;
48
}

孩子双亲表示法生成二叉树(类似于孩子表示法)

1
typedef struct BTnode{
2
    ElemType data;
3
    struct BTnode *firstchild, *sibling;
4
}BTnode, *BTree;
5
6
typedef struct Cnode{
7
    int child;
8
    struct Cnode *next;
9
}Cnode, *CList;
10
typedef struct CTnode{
11
    int parent;
12
    ElemType data;
13
    CList firstchild;
14
}CTnode, *CTbox;
15
typedef struct PCTnode{
16
    CTbox node;
17
    int r, n;
18
}PCTree;
19
20
void TransformPCTreeToBiTree(PCTree PC, BTree &BT, int root){
21
    if (root == -1){
22
        BT = NULL; return;
23
    }
24
    BT = (BTree)malloc(sizeof(BTnode));
25
    BT->data = PC.node[root].data;
26
    int rsave, tmp;
27
    if (PC.node[root].firstchild){
28
        rsave = PC.node[root].firstchide->child;
29
    }
30
    else{
31
        rsave = -1;
32
    }
33
    TransformPCTreeToBiTree(PC, BT->firstchild, rsave);
34
    tmp = PC.node[root].parent;
35
    if (tmp == -1){
36
        BT->sibling = NULL; return;
37
    }
38
    else{
39
        LList p = PC.node[tmp].firstchild;
40
        while (p && p->child != root){
41
            p = p->next;
42
        }
43
        if (p->next){
44
            rsave = p->next->child;
45
        }
46
        else{
47
            rsave = -1;
48
        }
49
        TransformPCTreeToBiTree(PC, BT->sibling, rsave);
50
        return;
51
    }
52
}

同构链式孩子表示法生成二叉树

1
typedef struct BTnode{
2
    ElemType data;
3
    struct BTnode *firstchild, *sibling;
4
}BTnode, *BTree;
5
6
#define DEGREE 5
7
typedef struct LCTnode{
8
    ElemType data;
9
    struct LCTnode *child[DEGREE];
10
}LCTnode, *LCTree;
11
12
13
BTree InitialTransLCTree2BiTree(LCTree root){
14
    if (!root){
15
        return NULL;
16
    }
17
    BTree BTroot = (BTree)malloc(sizeof(BTnode));
18
    BTroot->data = LCTree->data;
19
    BTroot->sibling = NULL;
20
    TransformLinkedChildTreeToBinaryTree(BTroot->firstchild, root, 0);
21
    return BTroot;
22
}
23
void TransformLinkedChildTreeToBinaryTree(BTree &BT, LCTree LCT, int i){
24
    if (i >= DEGREE || !LCT->child[i]){
25
        BT = NULL; return;
26
    }
27
    BT = (BTree)malloc(sizeof(BTnode));
28
    BT->data = LCT->child[i]->data;
29
    TransformLinkedChildTreeToBinaryTree(BT, LCT->sibling, i + 1);
30
    TransformLinkedChildTreeToBinaryTree(BT->child[i], LCT->firstchild, 0);
31
    return;
32
}

异构链式孩子表示法生成二叉树

1
typedef struct BTnode{
2
    ElemType data;
3
    struct BTnode *firstchild, *sibling;
4
}BTnode, *BTree;
5
6
#ifdef DEGREE
7
#undef DEGREE
8
#define DEGREE 5
9
#endif
10
11
typedef struct LCTnode{
12
    ElemType data;
13
    struct LCTnode * *child;
14
    int degree;
15
}LCTnode, *LCTree;
16
17
void TransformLCTree2BinaryTree(LCTree LCT, BTree &BT, int i){
18
    if (i >= LCT->degree || !LCT->child[i]){
19
        BT = NULL; return;
20
    }
21
    BT = (BTree)malloc(sizeof(BTnode));
22
    BT->data = LCT->child[i]->data;
23
    TransformLCTree2BinaryTree(LCT, BT->sibling, i + 1);
24
    TransformLCTree2BinaryTree(LCT->child[i], BT->firstchild, 0);
25
    return;
26
}
27
28
//Another Method:
29
void TransformLCTree2BinaryTree2(LCTree LCT, BTree &BT){
30
    if (!LCT->child[0]){
31
        BT = NULL; return;
32
    }
33
    BTree p, q;
34
    for (int i = 0; i < LCT->degree && LCT->child[i]; ++i){
35
        BTree q = (BTree)malloc(sizeof(BTnode));
36
        q->data = LCT->child[i]->data;
37
        q->sibling = NULL;
38
        q->firstchild = NULL;
39
        if (!BT){
40
            BT = q;
41
            p = q;
42
        }
43
        else{
44
            q->sibling = p->sibling; p->sibling = q;
45
            p = q;
46
        }
47
        TransformLCTree2BinaryTree2(LCT->child[i], q->firstchild);
48
        return;
49
    }
50
}

有两种方法的思路不同:前者是按单个节点完成递归,而后者则是按照层来递归(虽然二者都是深度优先),后者更像是图的遍历方法。

建堆O(n)时间复杂度证明

建堆复杂度先考虑满二叉树,计算完全二叉树建堆复杂度基本相同。

对满二叉树而言,第i层(根为第0层)有$2^i$个节点。由于建堆过程自底向上,以交换作为主要操作,因此第i层任意节点在最不利情况下,需要经过$(n-i)$次交换操作才能完成以该节点为堆根节点的建堆过程。因此,时间复杂度计算如下:

$T(n) = 2^0 * (n - 0) + 2^1 * (n - 1) + … + 2^n * (n - n) = sum((n - i) * 2^i)$

采用错位相减法:

  • 原式乘2得:
  • $T(n) * 2 = 2^1 * (n - 0) + 2^2 * (n - 1) + … + 2^{n+1} * (n - n) = sum((n - i) * 2^{i+1})$
  • 原式如下:
  • $T(n) = 2^0 * (n - 0) + 2^1 * (n - 1) + … + 2^n * (n - n) = sum((n - i) * 2^i)$
  • 相减得:
  • $2T(n) - T(n) = -n + 2^1 + 2^2 + … + 2^n = 2 * (1 - 2^n) / (1 - 2) - n = 2^{n+1} - 2 - n$

上面推导中,n为层数编号(自0层根节点开始)。故总节点数为$(1 + 2 + 4 + … + 2^n) = 2^{n+1} - 1$。渐进时,忽略减1取$N = 2^{n+1}$。

$T(N) = 2^{n+1} - n - 2 = N * (1 - logN / N - 2 / N) ≈ N$

故时间复杂度为$O(N)$,得证。

左偏树和斜堆

左偏树的性质

  • 本节点的键值key小于其左右子节点键值key(与二叉堆相同);
  • 本节点的左子节点的距离大于等于本节点的右子节点(这意味着每个节点中除了要存储键值外, 还需要一个额外的dist存储距离);
  • 节点的距离是其右子节点的距离+1(这意味着, 一个节点的dist是从它出发到达最近终端节点的距离);

斜堆的性质

  • 本节点的键值key小于其左右子节点键值key;
  • 斜堆节点不存储距离dist值, 取而代之的是在每次合并操作时都做swap处理(节省了存储空间);

大数乘法(Multiply Strings)

大数乘法的算法

大数乘法的关键在于如何用字符串来模拟大数乘法。方法有如下几种:模拟普通的手算乘法、利用代数方法优化的乘法、快速傅立叶变换FFT

各算法的优点

  • 模拟普通手算乘法:算法简单、空间复杂度小。时间复杂度为O(n^2)
  • 利用代数方法优化的乘法:使用递归求解,空间复杂度较大。算法复杂,需要定义大数加法大数减法。时间复杂度降低到O(n^1.5)
  • 快速傅立叶变换FFT:基于FFT的大数乘法时间复杂度O(nlogn)。快速傅立叶变换据数值分析老师说是本世纪最为伟大的算法。

下边主要对利用代数方法优化的乘法进行介绍。

分析

代数优化

  • 假设大数P、Q的长度为m和n,P = (A * 10^k + B)Q = (C * 10^k + D)
  • k = min(m / 2, n / 2)
  • PQ = (A * 10^k + B)(C * 10^k + D) = AC * 10 ^2k + (AD + BC) * 10^k + BD
  • 乘法操作作为主要操作,采用master定理可知,时间复杂度为O(n^2)。此时与普通的手算乘法并没有不同。
  • 用于减少时间复杂度的关键(A - B)(C - D) = AC - AD - BC + BD
  • 带入后得,AC * 10 ^2k + (AC + BD - (A-B)(C-D)) * 10^k + BD
  • 由于我们以乘法操作作为主要操作,因此每一层递归中只需要3次乘法。因此时间复杂度减少为O(n^1.5)
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×