就可以同时对这
个字符串进行匹配了，Trie树有一个很大的缺点，就是他所需要的空间是指数级别的，所有一般来说字符串的长度超过15的话我们就应该考虑别的方法了。最后是后缀数组，算法的主要精髓在于对于height数组的理解和应用，在国家队论文中有两篇文章是专门介绍后缀数组的，我这里就不赘述了。9图论包括最短路最小生成树强连通分量等知识点之所以把图论的内容放在最后讲完全是因为图论的知识点实在是太多了，涉及的方面也实在是太广了，我这里挑几个我题目做得比较多的方面来简单总结一下。首先就是最短路了，主要分为多源最短路，用的算法是非常经典的Floyd算法，复杂度为O
3，实现起来相当简单，主要就是DP的思想。还有单源最短路，最原始的方法是Bellma
Ford，但该算法使用的概率不高，因为他有一个非常好的替代品，就是SPFA，SPFA的实现有点类似广搜，代码也非常短，对于Bell
fma
Ford求一个图中是否存在负环的问题可以以完全地替代，另外在稀疏图中求最短路的效率甚至要高于用了优先队列优化过的Dijkstra，确实是一个实用的好东西。当然了，最为著名的Dijkstra算法是绝对不能不提的，该算法是我们求最短路时最常用的算法，但是由于他利用了贪心准则，所以一定要注意Dijkstra不能处理有负权边的图，D而ijkstra也有几个非常经典的变型，一个是将Dijkstra扩展到二维来求次短路，另一个是利用A来求次短路，大家是否注意到，学到后面的时候，不同知识块之间的分界已经越来越不清晰了，因为我们的脑中正在逐步形成一张知识网，将每一个知识点都有机地串联到了一起。第二个大点是最小生成树，该类问题也有两个广为人知的算法，适用于稠密图的Prim算法和适用于稀疏图的Kruscal算法该算法中要用
到并查集的算法，最小生成树同样有一些经典的变型，如次小生成树，最小限制度生成树等。再有一类非常重要的问题就是二分匹配问题，该问题涉及的知识点也是相当的多，求无权二分图的最大匹配有最为经典的匈牙利算法以及求带权的二分图的最小大匹配的KM算法，而由不带权的二分图的最大匹配数衍生出去的知识点有最小覆盖问题，最小路径覆盖问题等等，这块内容概念性比较强，其实说起来，图论最大的特点就是概念性强，变型极多，如果不深入地理解每一次问题及其经典算法，着实无法应变。最来就是欧拉回路问题，该类问题比较简单，无非就是两种，一个是判断图中是否存在欧拉回路，再一个就是求出该欧拉回路中的一条，实现起来也很简单，r