字符串算法
KMP算法
时间复杂度O(m+n)
主串与子串按位置比对，如果发现某一个位置不匹配，则寻找在子串该位置前的前缀长。
const int maxn = 1000005;
string s1, s2; //s1为主串，s2为子串
int next[maxn]; //next数组，保存了s1的前后缀交集的最长长度
void make_next() { //求解next数组
next[0] = 0; //首字母不与自己产生匹配
for (int i = 1, j = 0; i < s2.size(); ++i) { //字符串自匹配
while (j > 0 && s2[i] != s2[j]) j = next[j - 1]; //往前回溯
if (s2[i] == s2[j]) ++j;
next[i] = j; //记录前缀数
}
}
int kmp() {
for (int i = 0, j = 0; i < s1.size(); ++i) {
while (j > 0 && s1[i] != s2[j]) j = next[j - 1]; //不同就往前找前缀
if (s1[i] == s2[j]) ++j; //如果两者相同，则都向后检验
if (j == s2.size()) return i - j + 1;
}
return -1; //找不到返回-1
}字典树
Trie（经典字典树）
将字符串分割成单个字符进行存储，相同前缀的字符串共享前缀。适用于做前缀匹配的问题。
struct node {
node(char c) {
sum = end = 0;
ch = c;
}
int sum, end; //记录前缀出现的次数和单词的次数
char ch;
map<char, node*> mp;
};
class Trie {
private:
node* root;
public:
Trie() {
root = new node(' ');
}
void insert(string str) {
node* pos = root;
for (int i = 0; i < str.size(); ++i) {
map<char, node*>::iterator it = (pos->mp).find(str[i]); //查询单字符是否存在
if (it == (pos->mp).end()) { //找不到就创建一个节点
node* tmp = new node(str[i]);
pos->mp[str[i]] = tmp;
}
pos = pos->mp[str[i]]; //移动到下一位
++(pos->sum); //前缀出现次数+1
}
++(pos->end); //单词次数+1
}
int query(string str) {
node* pos = root;
// int ans=0;
bool flag = true; //默认可以查询到完整的单词
for (int i = 0; i < str.size(); ++i) {
map<char, node*>::iterator it = (pos->mp).find(str[i]); //查询单字符是否存在
if (it == (pos->mp).end()) { //查不到
flag = false;
break;
}
pos = pos->mp[str[i]]; //找得到接着找
// ans+=(pos->end);
}
if (flag) return (pos->sum);
else return 0;
}
};01字典树
将数据以二进制的方式进行存储，一般用于进行异或运算。存储的时候只需要存储0或1，所以可以将其看作是一棵二叉树。
以下是01字典树的数组写法（以最大异或对为例）：
const int MX = 100005;
int tot, son[MX * 30][2], a[MX];
void build(int x) { //建树
int p = 0;
for (int k = 30; k >= 0; --k) {
int tmp = (x >> k) & 1; //按照二进制的方式存储数据
if (!son[p][tmp]) son[p][tmp] = ++tot; //tot给对应的节点编号
p = son[p][tmp]; //下一个节点
}
}
int que(int x) {
int p = 0, ans = 0;
for (int k = 30; k >= 0; --k) {
int tmp = (x >> k) & 1;
if (son[p][!tmp]) { //从x的高位开始异或，尽量让高位为1
p = son[p][!tmp];
ans |= (1 << k);
}
else p = son[p][tmp]; //查询下一个节点
if (!p) break;
}
return ans;
}
int main() {
int n; cin >> n;
for (int i = 0; i < n; ++i) {
cin >> a[i];
build(a[i]);
}
int ans = 0;
for (int i = 0; i < n; ++i) ans = max(ans, que(a[i])); //对每一个数都求一次答案
cout << ans << endl;
return 0;
}最长异或路径
最长异或路径的解法是使用01字典树。
问题描述
给定一棵 n 个点的带权树，结点下标从 1 开始到 n。寻找树中找两个结点，求最长的异或路径。异或路径指的是指两个结点之间唯一路径上的所有边权的异或。
输入格式
第一行一个整数 n，表示点数。
接下来 n−1 行，给出 u,v,w ，分别表示树上的 u 点和 v 点有连边，边的权值是 w。
输出格式
一行，一个整数表示答案。
样例
样例输入 #1
4
1 2 3
2 3 4
2 4 6样例输出 #1
7解题思路
由异或的性值可得，对于树的任意路径<i, j>的异或值，均可由<root, i>和<root, j>两条路径的异或值异或而成，故可以先使用dfs计算出每一个顶点i到root的路径异或值Di，再将Di存储在数组sum[i]中，最后将问题转化为对sum[]数组求解最大异或数对。
最长异或路径(coding)
接下来使用C++类的写法来写01字典树的最长异或路径问题：
const int maxn = 100005;
int n, u, v, w, ans;
int sum[maxn]; //sum[i]表示第i个节点到root的异或值
bool mark[maxn]; //dfs辅助数组
struct node {
node(int _v, int _w) {
vertex = _v, weight = _w;
}
int vertex, weight;
};
struct Trienode { //模仿huffman树的构建方式，左0右1
Trienode() {
left = right = NULL;
}
Trienode* left;
Trienode* right;
};
class Trie {
private:
Trienode* root;
public:
Trie() {
root = new Trienode();
}
void insert(int x) {
Trienode* pos = root;
for (int i = 30; i >= 0; --i) {
int tmp = (x >> i) & 1; //取x的最高位
if (tmp) { //数位为1，存到右边
if (pos->right == NULL) pos->right = new Trienode();
pos = pos->right;
}
else { //数位为0，存到左边
if (pos->left == NULL) pos->left = new Trienode();
pos = pos->left;
}
}
}
int query(int x) {
int tmpans = 0;
Trienode* pos = root;
for (int i = 30; i >= 0; --i) {
int tmp = (x >> i) & 1; //取高位
if (tmp) { //数位为1，优先贪心0
if (pos->left != NULL) tmpans |= (1 << i), pos = pos->left;
else pos = pos->right;
}
else { //数位为0，优先贪心1
if (pos->right != NULL) tmpans |= (1 << i), pos = pos->right;
else pos = pos->left;
}
}
return tmpans;
}
};
vector<node> G[maxn]; //邻接矩阵存树
void dfs(int start, int index) {
mark[start] = 1; //标记已访问
for (int i = 0; i < G[start].size(); ++i) {
if (!mark[G[start][i]].vertex) {
sum[G[start][i].vertex] = index ^ (G[start][i].weight); //先利用dfs算出各点到根节点的异或值
dfs(G[start][i].vertex, sum[G[start][i].vertex]);
}
}
}
int main() {
cin >> n; //顶点数
for (int i = 1; i <= n - 1; ++i) {
cin >> u >> v >> w;
node n1(u, w), n2(v, w);
G[u].push_back(n2);
G[v].push_back(n1); //建树
}
dfs(1, 0);
Trie tree;
for (int i = 1; i <= n; ++i) tree.insert(sum[i]);
for (int i = 1; i <= n; ++i) ans = max(ans, tree.query(sum[i]));
cout << ans << endl;
return 0;
}