Bovine Genomics
暴力
str
hash+dp
设\(dp[i][j]\)为前\(i\)组匹配到第\(j\)位的方案数，则转移方程
\[dp[i][j+l]+=dp[i-1][j]
\]
\]
(\(j,l\)为满足题意的情况
通配符匹配
读题杀。dp
注意星号是可以匹配0个的。
按通配符分段，01表示是否能取到。
蚯蚓排队
留坑。
Seek the Name,Seek the Fame
kmp（利用next数组）
动物园
现场教学可还行
直接求就好
Censoring
模拟一个栈，next准备好，边压边弹
OKR-Periods of Words
利用next数组
最大周期=全部-最小公共前后缀
一直跳next就能求出
有一个while循环，会T，所以跳完以后把起点next直接设为结果
GT考试
\[f[i][j]=\sum\limits_{k=0}^{m-1}f[i-1][k]*g[k][j]
\]
\]
式子形式比较熟悉，可以矩阵快速幂优化
字符串的匹配
数的相对排名可以用树状数组处理，需要预先记录模式串里每个数的排名（记录\(<\)以及\(\leq\)的数量）
用kmp，匹配时把当时有用的数放到BIT里，跳next时记得删掉
如匹配成功，记录答案并跳next
Phone List
trie板子
The XOR Largest Pair
利用trie，把数转成二进制建01trie，然后尽量走01不同的
The XOR-longest Path
dfs出每个点到1的异或和，易得\(f(u,v)=f(1,u)\ xor\ f(1,v)\)
求最短路当然不能这样……但是因为有\(a\ xor\ a=0\)这个性质嘛
Nikitosh和异或
\(A[l_1]\ xor\ A[l_2]\ xor\dots xor\ A[l_n]=A_{pre}[l_n]\ xor\ A_{pre}[l_1-1]\)
后缀同理。
所以做一个前缀，做一个后缀，求最大的\(f(left)+f(right)\)