算法知识点

Trie树

字典树、前缀树

KMP算法

https://www.cnblogs.com/dusf/p/kmp.html

next数组：保存当前字符之前的字符串前缀和后缀最长重复子串长度

动态规划

dp数组

背包问题

有n个物品，物品对应的价值为W，费用是C，背包容量为V，每个物品只有一个可放可不放，求最大价值

for i in 0...n:
	for j in 0...V:
		dp[i][j] = max(dp[i-1][j], W[i]+dp[i-1][V-j])

AC自动机

红黑树

性质：

1. 每个结点要么是红的，要么是黑的
2. 根结点是黑的
3. 每个叶结点是黑的
4. 如果一个结点是红的，那么他的两个子结点是黑的
5. 对于任意结点，其到叶结点NIL的每条路径都包含相同数量的黑结点

左旋

右旋

Manacher算法

用来求某个字符串的最长回文子串

https://blog.csdn.net/coraline_m/article/details/10002791