## LCA(Lowest Common Ancestor)笔记（一）

LCA(Lowest Common Ancestor)笔记（一）

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

1. 当前结点本身

2.当前结点的左子树里

3.当前结点的右子树里

4.不存在这样的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;
}

（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;
}


#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）【非动态申请内存实现】

#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

#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是一种常用的高效的匹配算法，它减少了暴力匹配方法中一些不必要的匹配，特别是对于模式序列中有着明显重复的模式（如：aaaaaaab），能够提升匹配效率。

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

## Rabin-Karp Algorithm

Rabin-Karp Algorithm

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

$$c_n$$表示一个字符，所以$$c_1…c_n$$就是一个字符串。

$$hash(c_{s + 1}…c_{s + m + 1}) = (D * (hash(c_s…c{s + m}) – c_s*h) + c_{s + 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

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

## KMP (Knuth Morris Pratt) Pattern Searching

KMP (Knuth Morris Pratt) Pattern Searching

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;
}

Brute Force Pattern Search

【HDU – 1711】Number Sequence【KMP】

## ZWK线段树

$$[0, 7] \rightarrow [0, 3] \rightarrow [1, 3] \rightarrow [1, 2] \rightarrow [2, 2]$$

// 变量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;
}

$$n = 2^{log_{2}size}$$,