链式前向星，存图方法

此文为个人笔记，大学时候的总结难免有错，不代表本人目前水平[手动doge] (by 2021)

本来这总结已经被我从网络上删除了，看在可能是本文迄今为止唯一读者老田园的份上重新发布，方便老人查阅。

01背包

有n种物品，一个承重量为m的背包，每种物品最多只能拿一个或者不拿，且每个物品都有价值v[i]和重量w[i]，问怎么拿使背包内物品价值最大。

定义dp[i][j]表示走到第i个物品，背包重量为j时的价值。

转移方程dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])

dp[i-1][j]表示不拿当前物品，背包重量为j时的价值

RMQ区间最值查询，对于长度为n的数组A[]。

RMQ(i,j)，返回数组A区间[i , j]内的最大值或最小值。

思路：

(线段树也是可以的

ST算法：

O(nlogn)预处理，O(1)查询

求模式串在目标串中出现的次数和位置

next数组的一些性质

KMP最小循环节、循环周期：

定理：假设S的长度为len则S存在最小循环节，对S构造next数组，循环节的长度L为len-next[len]，子串为S[0…len-next[len]-1]。

回文串是指是正着读和反着读都一样的字符串，比如abcba。

最长回文子串是指在一个字符串中能找到的最长回文串，如这个字符串最长回文字串是最后6个字符：abacacbaaaab