c语言背包问题_c语言背包问题几种解法_背包问题贪心算法(5)

( 8 ).字符串(包括KMP算法,Trie树,后缀数组)

字符串处理也是ACM中相当大的一块知识面，而且也具有相当的实际应用面，其实对于字符串的知识我自己接触的也比较少，所以只能简单地谈一下几个最为基础的算法，KMP算法是两串匹配最为基础的线性算法，该算法的核心是对于next数组的理解，该数组是对于一个串进行了预处理得到的，从而成功将两串匹配的复杂度降到了线性。但KMP算法只能是两串之间的匹配，如果我们要多串匹配的话该怎么办呢？Trie帮助我们解决了这个难题，Trie其实是一颗字母树，树的每个节点都有26个英文字母，通过对这些节点的进行标记来插入一个字符串，在插入了n个字符串之后，我们就可以同时对这n个字符串之后我们就可以同时对这n个字符串进行匹配了，Trie树有一个很大的缺点，就是他所需要的空间是指数级别的，所有一般来说字符串的长度超过15的话我们就应该考虑别的方法了。最后是后缀数组，算法的主要精髓在于对于height数组的理解和应用，在国家队论文中有两篇文章是专门介绍后缀数组的，我这里就不赘述了。

(9).图论(包括最短路,最小生成树,强连通分量等知识点)

之所以把图论的内容放在最后讲完全是因为图论的知识点实在是太多了，涉及的方面也实在是太广了，我这里挑几个我题目做得比较多的方面来简单总结一下。首先就是最短路了，主要分为多源最短路，用的算法是非常经典的Floyd算法，复杂度为O(n^3)，实现起来相当简单，主要就是DP的思想。还有单源最短路，最原始的方法是Bellman-Ford，但该算法使用的概率不高，因为他有一个非常好的替代品，就是SPFA，SPFA的实现有点类似广搜，代码也非常短，对于Bellman-Ford求一个图中是否存在负环的问题可以以完全地替代，另外在稀疏图中求最短路的效率甚至要高于用了优先队列优化过的Dijkstra，确实是一个实用的好东西。当然了，最为著名的Dijkstra算法是绝对不能不提的，该算法是我们求最短路时最常用的算法，但是由于他利用了贪心准则，所以一定要注意Dijkstra不能处理有负权边的图，而Dijkstra也有几个非常经典的变型，一个是将Dijkstra扩展到二维来求次短路，另一个是利用A*来求次短路，大家是否注意到，学到后面的时候，不同知识块之间的分界已经越来越不清晰了，因为我们的脑中正在逐步形成一张知识网，将每一个知识点都有机地串联到了一起。

第二个大点是最小生成树，该类问题也有两个广为人知的算法，适用于稠密图的Prim算法和适用于稀疏图的Kruscal算法(该算法中要用到并查集的算法)，最小生成树同样有一些经典的变型，如次小生成树，最小限制度生成树等。再有一类非常重要的问题就是二分匹配问题，该问题涉及的知识点也是相当的多，求无权二分图的最大匹配有最为经典的匈牙利算法以及求带权的二分图的最小/大匹配的KM算法，而由不带权的二分图的最大匹配数衍生出去的知识点有最小覆盖问题，最小路径覆盖问题等等，这块内容概念性比较强，其实说起来，图论最大的特点就是概念性强，变型极多，如果不深入地理解每一次问题及其经典算法，着实无法应变。最来就是欧拉回路问题，该类问题比较简单，无非就是两种，一个是判断图中是否存在欧拉回路，再一个就是求出该欧拉回路中的一条，实现起来也很简单，一个DFS就可以完成了。还有就是强连通分量，该算法的核心就是对一个图求强连通分量后缩点，从而将一个图转化成一个有向无环图，从而方便我们进行接下去的操作。最后一个大块就是网络流了，该内容我涉及也比较少，主要就是几个求网络流的经典算法，如HLPP，ISAP，EK等等，网络流的变型也非常地多，需强加练习。

(10).ACM最终回之比赛篇

我参加过的正式比赛有两场，一场是大二下的上海邀请赛，另一场是大三上的合肥区域赛，由于水平有限，终究还是只拿了两块铜牌，下面我想谈一下组队的个人感受，首先是队员的构成，至少要有一个编码能力较强的人主要负责敲代码以增加出简单题的速度，另外就是数学基础较强的人，由于ACM现在越来越喜欢出数学题，而且数学好的往往思路会比较开阔，可以为整个团队提供想法，再有一个就是算法接触比较广的人，这一类的人接触的算法比较多，切题数也比较多，虽然可能没有哪个方面特别强，但其丰富的做题经验保证了他对于一道题的算法嗅觉，可以为整个团队指明方向。说到这里，我的总结也要结束了，希望大家可以从中可以获得帮助。

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/tongxinshuyu/article-24376-5.html