LCA(Lowest Common Ancestor)笔记(一)

LCA(Lowest Common Ancestor)笔记(一)

二叉搜索树(Binary Searching Tree)情形:

O(h)的方案,根据LCA的性质我们可以推测出,对于每一个结点,所要寻找的LCA结点一定是一下四种之一:

1. 当前结点本身

2.当前结点的左子树里

3.当前结点的右子树里

4.不存在这样的LCA(当且仅当输入的两个结点至少一个不存在于这棵树中)

对于二叉搜索树(Binary Searching Tree),两个结点分别在当前结点两侧(即一个结点小于等于当前结点,另一个结点大于等于当前结点)时,LCA恰好就是当前结点本身。当两个结点都小于当前结点,则根据BST的性质,可以知道LCA在当前结点的左子树中,反之在右子树中,如果深入到了叶子结点还没有找到,则说明这棵树中不存在当前结点。

递归实现:

#include <iostream>

using namespace std;

struct Node {
    int val;
    Node *left, *right;
    Node(int v = 0) : val(v) {
        left = right = nullptr;
    }
};

Node * lca(Node *root, int n1, int n2) {
    if (!root) return NULL;
    if (n1 < root->val && n2 < root->val)
        return lca(root->left, n1, n2);
    else if (n1 > root->val && n2 > root->val)
        return lca(root->right, n1, n2);
    else
        return root;
}

void delTree(Node *root) {
    if (!root) return;
    delTree(root->left);
    delTree(root->right);
    delete root;
}

int main(void) {
    // init the tree
    Node *root = new Node(20);
    root->left = new Node(8);
    root->right = new Node(22);
    root->left->left = new Node(4);
    root->left->right = new Node(12);
    root->left->right->left = new Node(10);
    root->left->right->right = new Node(14);

    // get LCA
    int n1 = 10, n2 = 14;
    Node *t = lca(root, n1, n2);
    printf("LCA of %d and %d is %d \n", n1, n2, t->val);

    n1 = 14, n2 = 8;
    t = lca(root, n1, n2);
    printf("LCA of %d and %d is %d \n", n1, n2, t->val);

    n1 = 10, n2 = 22;
    t = lca(root, n1, n2);
    printf("LCA of %d and %d is %d \n", n1, n2, t->val);

    // destroy tree
    delTree(root);

    return 0;
}

递推实现:

#include <iostream>

using namespace std;

struct Node {
    int val;
    Node *left, *right;
    Node(int v = 0) : val(v) {
        left = right = nullptr;
    }
};

Node * lca(Node *root, int n1, int n2) {
    while (root) {
        if (n1 < root->val && n2 < root->val)
            root = root->left;
        else if (n1 > root->val && n2 > root->val)
            root = root->right;
        else
            break;
    }
    return root;
}

void delTree(Node *root) {
    if (!root) return;
    delTree(root->left);
    delTree(root->right);
    delete root;
}

int main(void) {
    // init the tree
    Node *root = new Node(20);
    root->left = new Node(8);
    root->right = new Node(22);
    root->left->left = new Node(4);
    root->left->right = new Node(12);
    root->left->right->left = new Node(10);
    root->left->right->right = new Node(14);

    // get LCA
    int n1 = 10, n2 = 14;
    Node *t = lca(root, n1, n2);
    printf("LCA of %d and %d is %d \n", n1, n2, t->val);

    n1 = 14, n2 = 8;
    t = lca(root, n1, n2);
    printf("LCA of %d and %d is %d \n", n1, n2, t->val);

    n1 = 10, n2 = 22;
    t = lca(root, n1, n2);
    printf("LCA of %d and %d is %d \n", n1, n2, t->val);

    // destroy tree
    delTree(root);

    return 0;
}

 

对于更为一般的二叉树,我们的策略如下:

第一种,利用从根结点到两个目标结点的路径。利用这一性质的方案,大都具有O(h)复杂度,有些还需要额外存储空间。

(1)我们可以先走两次路径,分别是从根节点深搜到结点1,以及从根节点深搜到结点2,将两个路径记录到两个数组中,之后从这两个数组最开始的位置同时往后查,直到找到第一个不一样的点,这说明,在从根到两个结点的路径上,从这个结点开始以及之后的所有结点都不相同,而前面路径上的结点都相同,那么LCA就是这样第一个不相同的这组结点之前的一个结点。

(2)我们可以记录parent的位置,由于每个结点有一个独特的存储位置(如果是动态分配存储,这个位置就是地址,而如果使用静态数组进行存储,这个位置就是数组序号了),那么我们可以从第一个结点倒推会根节点,使用STL的map建立一个从结点存储位置值到表示该结点是否存在于路径中的布尔变量的一个映射(相当于一个Hash 表),利用这个,我们再从第二个结点倒推回根节点,路径上每个结点都尝试判断它是否被加入到了map中,找到的第一个存在于map中的结点,它便是LCA,使用set可以达到同样的效果。

代码:

#include <iostream>
#include <map>
#include <vector>

using namespace std;

struct Node {
    int val;
    Node *left, *right, *parent;
    Node(int v = 0, Node *p = nullptr) : val(v), parent(p) {
        left = right = nullptr;
    }
};

Node *lca(Node *n1, Node *n2) {
    map<Node *, bool> vis;
    while (n1) {
        vis[n1] = true;
        n1 = n1->parent;
    }
    while (n2) {
        if (vis[n2]) return n2;
        n2 = n2->parent;
    }
    return nullptr;
}

void delTree(Node *root) {
    if (!root) return;
    delTree(root->left);
    delTree(root->right);
    delete root;
}

int main(void) {
    // init the tree
    Node *root = new Node(1);
    root->left = new Node(2, root);
    root->right = new Node(3, root);
    root->left->left = new Node(4, root->left);
    root->left->right = new Node(5, root->left);
    root->right->left = new Node(6, root->right);
    root->right->right = new Node(7, root->right);

    // get LCA
    Node *n1 = root->left->left, *n2 = root->left->right;
    Node *ans;
    printf("LCA of %d and %d is %d\n", n1 ? n1->val : -1, n2 ? n2->val : -1, (ans = lca(n1, n2)) ? ans->val : -1);

    n1 = root->right->left, n2 = root->left->right;
    ans = NULL;
    printf("LCA of %d and %d is %d\n", n1 ? n1->val : -1, n2 ? n2->val : -1, (ans = lca(n1, n2)) ? ans->val : -1);

    n1 = nullptr, n2 = nullptr;
    ans = NULL;
    printf("LCA of %d and %d is %d\n", n1 ? n1->val : -1, n2 ? n2->val : -1, (ans = lca(n1, n2)) ? ans->val : -1);

    n1 = root->left, n2 = root->left->right;
    ans = NULL;
    printf("LCA of %d and %d is %d\n", n1 ? n1->val : -1, n2 ? n2->val : -1, (ans = lca(n1, n2)) ? ans->val : -1);

    n1 = root, n2 = root->left->left;
    ans = NULL;
    printf("LCA of %d and %d is %d\n", n1->val, n2->val, (ans = lca(n1, n2)) ? ans->val : -1);

    // destroy tree
    delTree(root);

    return 0;
}

 

(3)我们甚至可以不需要使用map这样的额外存储,当存储有parent位置后,我们需要的仅仅是找到它们路径上第一个共同的点是哪个,遇到问题仅仅是,由于两个点深度不同,倒推回根节点的过程中,它们“路过”那个要找的LCA结点的“时间”可能不同,这个问题其实很好解决,我们只要让它们的深度预处理到相同的就可以,我们只要将较深的结点先向前推几层,这个层数取决于两个结点在树中的层数差值,之后两个结点同时倒推,遇到的第一个公共点就是LCA结点。

代码:

#include <iostream>
#include <map>
#include <vector>

using namespace std;

struct Node {
    int val;
    Node *left, *right, *parent;
    Node(int v = 0, Node *p = nullptr) : val(v), parent(p) {
        left = right = nullptr;
    }
};

int getDepth(Node *n) {
    int ret = -1;
    while (n) {
        ret++;
        n = n->parent;
    }
    return ret;
}

Node *lca(Node *n1, Node *n2) {
    int d1 = getDepth(n1), d2 = getDepth(n2);
    if (d1 < 0 || d2 < 0) return nullptr;
    int diff = d1 - d2;
    if (diff < 0) {
        diff = -diff;
        Node *tmp = n1;
        n1 = n2;
        n2 = tmp;
    }
    while (diff--) n1 = n1->parent;
    while (n1 && n2) {
        if (n1 == n2) return n1;
        n1 = n1->parent, n2 = n2->parent;
    }
    return nullptr;
}

void delTree(Node *root) {
    if (!root) return;
    delTree(root->left);
    delTree(root->right);
    delete root;
}

int main(void) {
    // init the tree
    Node *root = new Node(1);
    root->left = new Node(2, root);
    root->right = new Node(3, root);
    root->left->left = new Node(4, root->left);
    root->left->right = new Node(5, root->left);
    root->right->left = new Node(6, root->right);
    root->right->right = new Node(7, root->right);

    // get LCA
    Node *n1 = root->left->left, *n2 = root->left->right;
    Node *ans;
    printf("LCA of %d and %d is %d\n", n1 ? n1->val : -1, n2 ? n2->val : -1, (ans = lca(n1, n2)) ? ans->val : -1);

    n1 = root->right->left, n2 = root->left->right;
    ans = NULL;
    printf("LCA of %d and %d is %d\n", n1 ? n1->val : -1, n2 ? n2->val : -1, (ans = lca(n1, n2)) ? ans->val : -1);

    n1 = nullptr, n2 = nullptr;
    ans = NULL;
    printf("LCA of %d and %d is %d\n", n1 ? n1->val : -1, n2 ? n2->val : -1, (ans = lca(n1, n2)) ? ans->val : -1);

    n1 = root->left, n2 = root->left->right;
    ans = NULL;
    printf("LCA of %d and %d is %d\n", n1 ? n1->val : -1, n2 ? n2->val : -1, (ans = lca(n1, n2)) ? ans->val : -1);

    n1 = root, n2 = root->left->left;
    ans = NULL;
    printf("LCA of %d and %d is %d\n", n1->val, n2->val, (ans = lca(n1, n2)) ? ans->val : -1);

    // destroy tree
    delTree(root);

    return 0;
}

 

第二种,和刚才BST中的解决策略类似,同样是考虑到上面所述的四种可能,只是我们不具有BST那样小的必然在左子树、大者必然在右子树那样的性质,于是我们需要遍历这棵树来解决,复杂度O(V)。

#include <iostream>
#include <vector>

using namespace std;

struct Node {
    int val;
    Node *left, *right;
    Node(int v = 0) : val(v) {
        left = right = nullptr;
    }
};

Node *lca(Node *root, int n1, int n2) {
    if (!root) return NULL;
    if (root->val == n1 || root->val == n2)
        return root;
    Node *left = lca(root->left, n1, n2);
    Node *right = lca(root->right, n1, n2);
    if (left && right) return root;
    return left ? left : right;
}

void delTree(Node *root) {
    if (!root) return;
    delTree(root->left);
    delTree(root->right);
    delete root;
}

int main(void) {
    // init the tree
    Node *root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);
    root->right->left = new Node(6);
    root->right->right = new Node(7);

    // get LCA
    int n1 = 4, n2 = 5;
    Node *ans;
    printf("LCA of %d and %d is %d\n", n1, n2, (ans = lca(root, n1, n2)) ? ans->val : -1);

    n1 = 6, n2 = 5;
    ans = NULL;
    printf("LCA of %d and %d is %d\n", n1, n2, (ans = lca(root, n1, n2)) ? ans->val : -1);

    n1 = 8, n2 = 9;
    ans = NULL;
    printf("LCA of %d and %d is %d\n", n1, n2, (ans = lca(root, n1, n2)) ? ans->val : -1);

    n1 = 2, n2 = 5;
    ans = NULL;
    printf("LCA of %d and %d is %d\n", n1, n2, (ans = lca(root, n1, n2)) ? ans->val : -1);

    n1 = 1, n2 = 4;
    ans = NULL;
    printf("LCA of %d and %d is %d\n", n1, n2, (ans = lca(root, n1, n2)) ? ans->val : -1);

    // destroy tree
    delTree(root);

    return 0;
}

 

字典树(Trie)【非动态申请内存实现】

字典树(Trie)【非动态申请内存实现】

程序竞赛中常常会用到字典树,我们知道,通常的竞赛中数据量是给定大小的,那么我们便不必要动态申请内存去创建字典树,我们完全可以通过预先开数组的方法来实现这棵字典树,以避免new或者malloc的时间消耗。

数组实现版:

#include <iostream>
#include <string>
#include <cstring>

using namespace std;

const int SIZE_OF_ALPHABET = 26;
const int LIM = 200;
const int NIL = -1;
struct Node {
    int idx[SIZE_OF_ALPHABET];
    bool isEndOfWord;
} trie[LIM];
int len = 0;

void init() {
    len = 0;
    for (int i = 0; i < LIM; i++) {
        memset(trie[i].idx, NIL ,sizeof(trie[i].idx));
        trie[i].isEndOfWord = false;
    }
}

void insert(const string &str) {
    int crt = 0;
    for (int i = 0; i < str.size(); i++) {
        int key = str[i] - 'a';
        if (trie[crt].idx[key] == NIL) trie[crt].idx[key] = ++len;
        crt = trie[crt].idx[key];
    }
    trie[crt].isEndOfWord = true;
}

bool query(const string &str) {
    int crt = 0;
    for (int i = 0; i < str.size(); i++) {
        int key = str[i] - 'a';
        if (trie[crt].idx[key] == NIL) return false;
        crt = trie[crt].idx[key];
    }
    return trie[crt].isEndOfWord;
}

int main(void) {
    init();
    /* Do something here */
    return 0;
}

 

vector+map实现:

#include <iostream>
#include <map>
#include <vector>
#include <string>

using namespace std;

struct Node {
    map<char, int> idx;
    bool EOW;           // the end of word
    Node() : EOW(false) {}
};
vector<Node> trie;

inline void init() {
    trie.clear();
    // create the head node
    trie.push_back(Node());
}

void insert(const string &str) {
    int crt = 0;
    for (int i = 0; i < str.size(); i++) {
        if (!trie[crt].idx[str[i]]) {
            trie[crt].idx[str[i]] = trie.size();
            trie.push_back(Node());
        }
        crt = trie[crt].idx[str[i]];
    }
    trie[crt].EOW = true;
}

bool query(const string &str) {
    int crt = 0;
    for (int i = 0; i < str.size(); i++) {
        if (!trie[crt].idx[str[i]]) return false;
        crt = trie[crt].idx[str[i]];
    }
    return trie[crt].EOW;
}

int main(void) {
    init();
    /* Do something here */
    return 0;
}

 

模式匹配中的一些小技巧以及一些杂乱的东西

模式匹配中的一些小技巧以及一些杂乱的东西

关于模式匹配问题,有一些比较杂的内容我不太清楚应该归类到哪里,其中有一部分一般可能无法派上用场,但是有一些也十分重要,因此全放到了这里。

  1. 如果模式序列中所有元素都不相同,那么在使用暴力模式匹配方法 (Brute Force Pattern Search) 时可以做一点微小的优化,如果我们在i处发现长序列与模式序列的第一个元素一样,这时我们会开始逐个元素匹配,如果在模式序列的第j处发现一个不匹配的字符,那么我们可以直接从i + j + 1处开始继续从模式序列的第一个元素开始尝试匹配,而不用再从i  + 1处开始,这得益于模式序列中所有元素都不相同。【从感觉的角度上想,这其实也略微有一些KMP (KMP (Knuth Morris Pratt) Pattern Searching) 的思想】
  2. 如果长序列长度n等于模式序列长度m,那么我们可以不使用任何复杂的模式匹配算法,直接遍历尝试匹配,复杂度O(n)。
  3. 显然,如果长序列的长度n小于模式序列的长度m,必然无法完成匹配,如果在输入数据不保证n大于等于m的时候,我们应当进行额外的检查。

Brute Force Pattern Search

Brute Force Pattern Search

模式匹配 (Pattern Searching)

暴力模式匹配,也可以叫做简单模式匹配。它的逻辑十分简单,代码容易实现。给出一个长序列和一个模式序列(常是字符串,或者一串数),要在长序列中找到模式序列的出现位置、出现次数等。最直接能想到的方法就是这种,对于长度为n的长序列、长度为m的模式序列,只要写两层循环,暴力尝试m*n种匹配方式,即O(mn)复杂度,就可以找到。缺点是十分耗时。

#include <iostream>
#include <string>

using namespace std;
void search(const string &pat, const string &txt) {
    int pat_len = pat.size();
    int txt_len = txt.size();
    for (ULL i = 0; i <= txt_len - pat_len; i++) {
        if (pat[0] == txt[i]) {
            int j;
            for (j = 1; j < pat_len; j++) {
                if (pat[j] != txt[i + j]) break;
            }
            if (j == pat_len) {
                /*
                 *  found the pattern string
                 *  do something here
                 */
            }
        }
    }
}

int main(void) {

    return 0;
}

相关阅读:

KMP (Knuth Morris Pratt) Pattern Searching:

KMP是一种常用的高效的匹配算法,它减少了暴力匹配方法中一些不必要的匹配,特别是对于模式序列中有着明显重复的模式(如:aaaaaaab),能够提升匹配效率。

Rabin-Karp Algorithm

Rabin-Karp Algorithm利用提前比较hash值来减少暴力匹配的次数,它优越的关键在于给出了由一个序列hash值求得下一个序列hash值的O(1)时间复杂度方法。

Rabin-Karp Algorithm

Rabin-Karp Algorithm

模式匹配 (Pattern Searching)

解决问题:

同样是解决字符串匹配问题的算法,即在一个长字符串中寻找模式字符串出现的位置。复杂度O(mn),m和n依次是模式串的长度和长字符串的长度,这样看起来似乎与暴力的方法(或者叫简单模式匹配方法)没有区别,但是在实际使用中,它常常被认为复杂度是O(m + n)的。

实现方法很简单,就是在暴力匹配的方法基础上加入hash值。

\(hash[c_1c_2…c_n] = c_1 * D^{n – 1} + c_2 * D^{n – 2} + … + c_n * D^1\)

其中D是字符表的大小,通俗来说,就是总共可能有多少种字符。

\(c_n\)表示一个字符,所以\(c_1…c_n\)就是一个字符串。

由于我们想要放到int中,我们会将其对Q取模,Q是一个任意素数。

由于模式串长度固定,我们刚开始在要寻找模式串的字符串中将开头前m个字符算出hash值,同时也算出模式串的hash值,接着首先比较hash值,如果一样再逐个字符比较一下, 如果不一样直接考虑下一段字符串。而这个算法优越性的核心就在于它找出了复杂度为O(1)的由上一段字符串算下一段字符串的公式:

\(hash(c_{s + 1}…c_{s + m + 1}) = (D * (hash(c_s…c{s + m}) – c_s*h) + c_{s + m + 1}) \% Q\)

其中,\(h = d^{m – 1} % Q\),可以使用快速模幂来求。

#include <iostream>
#include <string>

using namespace std;

const int D = 256;      /* D is the number of characters in the alphabet */
const int Q = 1e7 + 19;      /* a prime number */

string pat, txt;

int powMod(int x, int n) {
    int ret = 1;
    while (n) {
        if (n & 1) ret = ret * x % Q;
        x = x * x % Q;
        n >>= 1;
    }
    return ret;
}

void search() {
    int pat_len = pat.size();
    int txt_len = txt.size();
    int h = powMod(D, pat_len - 1);
    int p = 0, t = 0;
    for (int i = 0; i < pat_len; i++) {
        p = (p * D + pat[i]) % Q;
        t = (t * D + txt[i]) % Q;
    }
    for (int i = 0; i <= txt_len - pat_len; i++) {
        if (p == t) {
            int j;
            for (j = 0; j < pat_len; j++)
                if (pat[j] != txt[i + j]) break;
            if (j == pat_len) {
                /*
                 *  found the pattern string
                 *  do something here
                 */
            }
        }
        /* 算到最后一个后就不要再尝试算下一个hash了,否则会越界 */
        if (i < txt_len - pat_len)
            t = (D * (t - txt[i] * h) + txt[i + pat_len] + Q) % Q;      // 加Q防止负数
    }
}

int main(void) {

    return 0;
}

 

相关阅读:

Brute Force Pattern Search

图说Rabin-Karp字符串查找算法

 

可能会用到的:

10000019至10001659之内的大质数(素数)表

KMP (Knuth Morris Pratt) Pattern Searching

KMP (Knuth Morris Pratt) Pattern Searching

模式匹配 (Pattern Searching)

解决问题:

寻找一段长字符串中的模式字符串,问题通常为求模式字符串出现次数、第一次出现模式字符串的位置等。

这里讨论的是KMP方法,这个方法对传统的简单匹配方法进行了优化。为了方便理解KMP方法的优势,先大致说明一下简单匹配方法,简单的匹配方法具有\(O(m * n)\)的复杂度,它的策略是:遍历长字符串中的每一个字符,并尝试与模式字符串的第一个字符进行匹配,如果它们相同,则开始尝试将模式字符串剩下的部分与长字符串从这个字符处开始之后的部分依次匹配,遇到不匹配的字符便中止,重新回到外层循环,继续遍历长字符串中的每一个字符;而如果刚才内层循环的匹配操作可以持续到模式字符串末尾,则说明成功找到了一个匹配字符串。

简单匹配方法十分好理解,但是缺点也十分明显,如下这个例子,假设:

模式字符串为:aaaaaac

长字符串为:acaacaaaacaaaaaacaaaaaaaaac

在诸如此类模式字符串中有很多重复模式的时候,使用简单匹配方法常常会需要遍历多次模式字符串,而我们其实是可以事先根据模式字符串中的重复模式知道,重复这样的无意义匹配是无意义的,KMP算法便是消除这种无意义匹配的一种解决方案。

对于模式字符串:aabaaa,为了方便这里表示,将这五个字符依此用①②③④⑤⑥来表示。如果我们匹配成功了①,而匹配失败了②,我们接下来应该用①来尝试匹配;如果我们匹配成功了②,匹配失败了③,我们应该使用②来尝试匹配,因为对于子字符串aa,它的前缀a和后缀a是相同的,由于前一个字符位置上匹配成功了②,所以①也必然匹配前一个字符,所以直接使用②来尝试匹配当前字符;中间略过几种情况,假如我们已经匹配成功了④和⑤,当前字符匹配失败了⑥,那么我们接着应该直接用③来尝试和当前的字符匹配,原因是前缀①②与后缀④⑤相同。【前缀能不包括最后一个字符,同样地,后缀也不能包括第一个字符】

为了确定中间应当略过几个字符,使用KMP方法时,需要预先根据模式字符串建立一个数组,假设叫做kmp[],其中kmp[i]存储的是前i + 1个字符中,最长的前后缀相同子字符串的长度,对于上边的aabaaa,kmp[0]表示子字符串a,故kmp[0] = 0;kmp[1]表示的是子字符串aa,由于最长前缀a和后缀a相同,所以kmp[1] = 1;kmp[2]表示的是子字符串aab,前缀a、aa都无法与任何后缀b、ab相同,所以kmp[2] = 0;由此可接着得到kmp[3] = 1, kmp[4] = 2, kmp[5] = 2.

实现的时候,我们可以这样做:首先让kmp[0] = 0,之后给定一个变量k = 0,可以理解成当前第一个要匹配的字符,也就是除去当前长度下最长相同前后缀后的第一个字符在模式字符串数组中的位置,接下来我们从i = 1开始遍历模式字符串,对于每个字符,尝试将pat[k]与pat[i]匹配,如果成功匹配,就可以将k加1,并且将这个值放入到kmp[i]中;如果匹配失败,则将k尝试去上一次的值,也就是在比当前字符少一个字符时的最大相同前缀后的一个字符的位置,即kmp[k – 1]的值,如果仍然不匹配,则继续这样做,直到匹配或k到达0。当k到达0时,pat[0]即是第一个字符,如果它仍然不能和当前字符匹配,则说明kmp[i] = 0,反之则是只有这一个字符匹配成功,kmp[i] = 1。这样就可以建立好kmp数组。

再次说明一下:kmp[i]表示的是模式字符串前i + 1个字符中,最长的相同前后缀的长度,假设长度为L,由于模式字符串中的字符下标从0开始,所以刚好0~L – 1就是这个前缀,每次比较便可以从L处开始,即kmp[i]处开始。

用类似的办法来进行模式匹配,从k = 0、i = 0开始,匹配模式字符串pat[k]与长字符串txt[i],如果相同,就k++, i++后接着匹配,其间留意检查k是不是已经达到pat字符串的长度,是的话,要将它的值置为kmp[k – 1]。

还有一点注意点是:由于下面代码while循环中的一个条件是k < 0,所以即便结束了这个循环也无法保证一定是匹配成功,可能仅仅是因为k归0了,所以要再用if来判断是否匹配成功。

C++实现如下:

#include <iostream>

using namespace std;

const int LIM = 10;             /* The maximum length of pattern string */
int kmp[LIM];

void build(string &pat) {
    kmp[0] = 0;
    int k = 0;
    int len = pat.size();
    for (int i = 1; i < len; i++) {
        while (k > 0 && pat[k] != pat[i])
            k = kmp[k - 1];
        if (pat[k] == pat[i]) kmp[i] = ++k;
        else kmp[i] = 0;
    }
}

void kmpSearch(string &txt, string &pat) {
    build(pat);
    int k = 0;
    int len = txt.size();
    int pl = pat.size();
    for (int i = 0; i < len; i++) {
        while (k > 0 && pat[k] != txt[i])
            k = kmp[k - 1];
        if (pat[k] == txt[i]) k++;
        else k = 0;
        if (k == pl) {
            /*
             *  found the pattern string
             *  do something here
             */
            k = kmp[k - 1];
        }
    }
}

int main(void) {

    return 0;
}

如果模式字符串比LIM设定的大,需要修改LIM的值。

成功匹配到模式字符串后进行的操作,请放在/* do something here */注释后。

上边实现的关键:(1)kmp数组的下标表示长度为下标+1的子串,值是该子串的最大相同前后缀长度,因此匹配失败时k赋值kmp[k – 1]。(2)kmp数组中的值虽然是最大相同前后缀的长度,但也恰好是模式串中接下来需要尝试匹配的字符的序号(如果字符串的序号是从0开始的话)。(3)回到k = 0跳出循环后也要记得再做一次判断,决定是否要增加k。

 

相关阅读:

Brute Force Pattern Search

 

相关问题:

【HDU – 1711】Number Sequence【KMP】

ZWK线段树

前言一:

建议在阅读这篇博客前,首先会实现普通的递归线段树。

前言二:

此方法非本人所创,为从其他人博客学习而来。普通用途下(如求和、RMQ等),这个方案能够获得比普通线段树更少的时间消耗,但是使用时也有一些细节值得注意(详见正文),经过几次掉入这些细节的坑中后,我决定将它记录下来。

正文:

首先,我们需要回忆一下一般线段树的点更新操作过程:

假设要构建对一个包含8个元素的数组进行更新与求和的线段树,

假设数组元素序号区间范围是[0, 7],并且现在需要更新2号元素,于是,我们按着:

\([0, 7] \rightarrow [0, 3] \rightarrow [1, 3] \rightarrow [1, 2] \rightarrow [2, 2]\)

这样的深入顺序寻找到了目标位置。

类似的,求任意区间的和,比如[2, 5]便是将表示区间为[2, 2], [3, 3], [4, 5]的三个结点存储的值求和,便得到了数组元素[2, 5]的和。

接下来讨论一下如何不使用递归来构建这棵线段树。首先我们需要将区间转化一下,以方便接下来的操作,按照上边的例子,元素序号的区间范围是[0, 7],在序号都是整数的情况下,它等价于[0, 8),如果以[0, 8)作为根节点区间,构建出来的线段树将会如下图,是一棵满二叉树:

这里稍稍做一下说明:在上面这张图中,颜色较深的方格表示的是对应结点在线段树数组中的索引,而颜色较浅的方格则表示的是对应结点代表的区间。

我们可以看到,最后一行的八个结点,就是原始数组中的八个数,他们在线段树中的位置是从8开始到15结束的,这是必然的,对于一棵有n片叶子的满二叉树(备注:这便要求n是2的幂),非叶子结点的个数为\(n – 1\),如果根节点索引是1,则从做到右的第一片叶子的索引一定是n。

由于能够直接找到每个数组元素在线段树中的确切位置,对线段树进行初始化、更新、询问的操作就可以从底部向上进行。

现在总结一下这个算法的核心:如果有n个元素,则i号元素在线段树数组中的索引为\(i + n\)。

下面是三个核心函数的C++代码实现:

// 变量n是data数组中元素的个数
// 数组STree就是线段树数组
void build() {
    // 这第一个循环是将存放在data数组中的原始数据存放到每个对应的叶子上
    for (int i = 0; i < n; i++) {
        STree[n + i] = data[i];
    }
    // 接下来开始从底向上遍历一下所有的结点,进行一次初始化
    for (int i = n - 1; i > 0; i--) {
        STree[i] = STree[i << 1] + STree[i << 1 | 1];
    }
}

void update(int idx, int diff) {
    //idx表示第idx号元素,idx + n就是它在线段树数组中对应叶子的索引值
    STree[idx + n] += diff;
    for (idx += n; idx &gt; 1; idx >>= 1) {
        STree[idx >> 1] = STree[idx] + STree[idx ^ 1];
    // 这里进行与1异或的作用是:在这棵满二叉树中,如果一个结点
    // 是左结点,则它的索引值是一个偶数,则右结点的索引就是将其
    // 索引值二进制表示下最低位换成1;反过来,对于一个右结点,它
    // 需要将二进制表示下的最低位换成0.
    }
}
    // 由于为了构建满二叉树时,我们将这棵线段树的区间修改成了左闭右开区间,所以这里getSum函数获得的是区间[from, to)的和
int getSum(int from, int to) {
    int res = 0;
    for (from += n, to += n; from < to; from >>= 1, to >>= 1) {
    // 对于左边界,如果它是一个右结点,由于其父结点包含了不属于求和
    // 区间的左结点,所以应当抛弃,而直接将当前节点的值加入到函数返回值中
        if (from&1)
            res += STree[from++];
    // 对于右边界,考虑到右边界上的值是不计入求和的,如果它是一个右结点,我们就先将索引值减一,得到左结点,接着将左结点的值加入到返回值中。
        if (to&1)
            res += STree[--to];
    }
    return res;
}

 

最后,来讨论一下最开始提到的细节。如果想要正确使用这棵树,就必须保证构造一棵满二叉树,这样才能够保证数组元素序号与线段树叶子的序号的对应关系成立,这个算法才是正确的。

对于任意个数的数据,假设为size,则应有:

\(n = 2^{log_{2}size}\),

将根节点的区间设置为[0, n),第一片叶子的序号是n,树的大小为2 * n – 1.