ACM集训队阶段总结课件

浙江林学院

ACM集训队阶段总结WritebyZhuangli(zjfc3)

浙江林学院

ACM集训队阶段总结1图论

Whatisthat?图论

Whatisthat?2什么是图论?图论〔GraphTheory〕是数学的一个分支。它以图为研究对象。图论中的图是由若干给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系。图论本身是应用数学的一部份，因此，历史上图论曾经被好多位数学家各自独立地建立过。关于图论的文字记载最早出现在欧拉1736年的论着中，他所考虑的原始问题有很强的实际背景。

什么是图论?图论〔GraphTheory〕是数学的一个分支3并查集及其拓展并查集是一种信息内聚很强的数据结构，它在判定图的连通性以及等价类划分的时空效率上有着不可替代的优势。但并查集的特殊应用也应该有所了解. 以下两类是并查集在实际问题中的特殊拓展，希望大家能够进行快速掌握.1.集合计数问题2.二分图识别并查集及其拓展并查集是一种信息内聚很强的数据结构，它在判定图4集合计数问题HDU1856Moreisbetter题意： 若A与B认识，B与C认识，则A与C认识，现给你一组人员的关系表，求在这样的不同群组内，拥有最多人数群组的人数。集合计数问题HDU1856Moreisbetter5集合计数问题有什么想法？并查后统计并查数组?不可行数据范围10000000如果逐个统计必定TLE不能如此暴力….思路如何……想3分钟集合计数问题有什么想法？6集合计数问题联想到并查集的构造原理构造rank数组,在并操作中入手！！好,问题解决!!

集合计数问题7二分图识别HDU1829ABugOfLife题意： 假定两只飞虫(Bug)关系表，如AB表示A仰慕B，问是否存在同性的飞虫互相仰慕（也就是同性恋问题）.二分图识别HDU1829ABugOfLife8二分图识别难点：A与B的集合归属不定如何解决?思考！！！二分图识别9二分图识别非此即彼思想的运用构造数组opp，初始化为本身编号，若A与B有关，首先进行find(A),find(B)的操作，若根相同，则说明A与B属于同一集合，即同性恋，否则执行下面的操作，如果A的opp等于本身，说明A的opp未初始化，使之等于B，否则将A的opp与B进行Unition操作，类似的如果B的opp等于本身，说明B的opp未初始化，使之等于A，否则将B的opp与A进行Unition操作二分图识别10二分图识别想想为什么？二分图的性质决定更深入的二分识别……(如统计最小单元集，如何进行>_<课后思考!)二分图识别11最短路径问题在一个网络图中求解一点到另一点间最短距离及其路径的算法称之为最短路径问题。1、单源正权最短路径2、单源带负权最短路径3、多源最短路径最短路径问题在一个网络图中求解一点到另一点间最短距离及其路径12单源正权最短路径求解单源最短路径的Dijkstra算法，状态转移与贪心准则的完美结合。思想：动态规划策略：贪心(O(Ve))步骤：

1.构造辅助数组Dis[],Vist[],Dis[i]表示从源点出发到达i点的最短距离,Vist[i]表示i点是否已被访问，算法开始执行时令所有Dis[i]=w(start,i)[不可达为MAX],Vist[start]=true.

2.每次得到Dis[]数组中最小且未被访问过的点i，标记Vist[i]=true,遍历所有与i相关的边，若得到Dis[i]+w(i,j)<Dis[j]，则更新Dis[j]=Dis[i]+w(i,j).

3.如此循环直到所有点均被标记.单源正权最短路径求解单源最短路径的Dijkstra算法，状态13单源正权最短路径Dijkstra的致命弱点：不能处理带负权的边思考：Why?问题出自贪心策略！！若存在负权，则算法将不断更新负权边相关顶点的Dis值，从而导致答案错误!单源正权最短路径Dijkstra的致命弱点：不能处理带负权的14单源带负权最短路径如何处理Dijkstra的遗留问题？摈弃贪心策略执行松弛技术-----Bellman-ford算法单源带负权最短路径15单源带负权最短路径什么是松弛技术？日常生活中的例子~~（1+1猜想）松弛技术的本质是首先给予一个物体很高的估价，在每次的迭代中对估价进行修正，在有限次的迭代后使估价与实际值吻合的技术。单源带负权最短路径什么是松弛技术？16单源带负权最短路径思想：若存在N个点的网络，则对于起点到终点最多经过N-1条边策略：有限迭代下的松弛技术单源带负权最短路径17单源带负权最短路径步骤：1、开辟辅助数组Dis[],记录源点到点i的最小距离，初始时设所有Dis[]值为MAX，Dis[start]=0.2、进行n-1次迭代，对于所有边，若满足Dis[i]<MAX&&Dis[i]+w(i,j)<Dis[j],更新Dis[j]=Dis[i]+w(i,j).3、执行完成后，再执行1次迭代，若出现Dis[i]+w(i,j)<Dis[j]的情况，则表明出现了负环，此时不存在最短路径，否则Dis[end]即所求单源最短路径.单源带负权最短路径步骤：18单源带负权最短路径算法分析：1、迭代v-1次，每次遍历所有边,复杂度O（VE）,E为全部边，Dijkstra的复杂度O(Ve),e为部分边…..效率差别很大!!2、如何优化？思考！！单源带负权最短路径算法分析：19单源带负权最短路径优化1：使用bool值Y标记此次迭代是否进行松弛，若没进行松弛表明已经得到最短路径，因此跳出循环。（常系数优化）--YEN氏优化优化2：使用标记数组以及队列辅助，初始化时推入start点，标记start在队内，每次执行时，将队首推出，标记其不在队内，遍历其邻边，进行松弛操作，将所有不在队内且进行过松弛操作的边相关的点入队直到队列为空（即不再进行松弛操作）--SPFA！！单源带负权最短路径20单源带负权最短路径由优化2得到的正是传说中的SPFA，拥有神一般的效率O（KE），K一般取值3-5。算法如其名ShortestPathFastAlgorithm!瓶颈：如何判负环？思考！！！当一个点入队次数超过边的次数！需要辅助数组统计各点入队次数，此时的空间与时间效率都极低！！因此此算法在稠密带负环图中的表现不如bellman-ford的YEN氏优化！！请大家慎重选择使用。单源带负权最短路径由优化2得到的正是传说中的SPFA，拥有神21多源最短路径当题目要求大量的查询工作时，需要一种算法能在多项式时间内得到所有顶点间的最短距离并保存结果备查。Floyed算法应运而生!!多源最短路径22多源最短路径思想：传递关系闭包策略：动态规划O(V*V*V)步骤：1、对于点k，若存在w(i,k)+w(k,j)<w(i,j)，则更新w(i,j)=w(i,k)+w(k,j).2、迭代k直到结束多源最短路径思想：传递关系闭包23多源最短路径算法分析：1、不论正负权，大小通吃2、一次计算，次次查询3、可扩展性强！（关系传递，最长路径）多源最短路径算法分析：24图的遍历对于网络图G，如何不失一般性的搜索各结点—图的遍历.DFS(深度优先)BFS(广度优先)--不再一一评述图的遍历对于网络图G，如何不失一般性的搜索各结点—图的遍历.25图的表示邻接阵：对于拥有稠密边的图是个很好表示方法隆重推出~_~邻接表：在图的边数有限，点数过多时是一个很好的表示，主要的效率消耗在于结点的动态生成,然而有一种方法……使得动态的表达静态化…效率神一样的提高……图的表示26静态邻接表ZJFC-1236环球旅行题意:~~中文题自己看!!!静态邻接表27静态邻接表演示Sample的代码优点1、使用辅助数组p[]，p[i]为p点邻接的边号，若为-1则表示无边相关，否则可据此访问边数组，通过next值遍历该点邻接的所有边优点2、空间是边相关的O（E），而不是邻接阵的O（V*V），想想吧,V为10W对于邻接阵的恐怖概念…优点3、插入操作时，执行三步曲，使表结构成链状，p[]数组得到更新，具有很高的技巧性，对于每次操作只需对p数组的初始化，而不需要对边表进行改动，从动态向静态转变！静态邻接表演示Sample的代码28静态邻接表邻接表下对Dijkstra的优化上面讲过其时间效率O（Ve）是基于邻接表，而在邻接阵中是O（V*V*V），使用静态邻接表本身就是场轰轰烈烈的优化！使用优先队列（二叉堆）！由于使用到贪心策略，我们可以很好想象，优化每次GetMin的操作，即将Dis数组撤消，转换做优先队列，每次取与更新Dis值从原先的O（E+V）转换为O（logV）,算法总效率提高到O（VlogV)静态邻接表29静态邻接表对于环球旅行题目的求解步骤1、使用map(红黑树)进行键值关联2、构造静态邻接表3、二叉堆优化下的Dijkstra求解静态邻接表30最小生成树对于连通下的带权网络图G，存在一个经过所有点而不成回路的连通，使其权和为本网络最小，称为最小生成树。应用：最小代价网络。方法1：Prim算法方法2：Kruskal算法最小生成树对于连通下的带权网络图G，存在一个经过所有点而不成31Prim算法对Dijkstra算法的推广，主算法几乎一模一样。思想：贪心步骤1：第一次首先选择最小的边，并标记边的2个端点步骤2：以后的每次操作都是在被标记点为起点，未被标记点为末点中取最小边，执行连接，并标记末点，直到所有的点被标记Prim算法对Dijkstra算法的推广，主算法几乎一模一样32Prim算法复杂度为O（VE），想想还有什么更好优化？对!贪心策略的优化一般使用优先队列实现，使GetMin操作为O(logE)！于是整体复杂度为O（VlogE）效率大大提高Prim算法复杂度为O（VE），想想还有什么更好优化？33Kruskal算法一种无视顶点的操作进行该操作需要边结构与并查集思想：贪心优先队列优化！步骤：1、得到边序列推入优先队列2、每次得到一条边，使用并查集判断是否连通，若连通则执行并操作。3、迭代直到执行|V|-1次操作Kruskal算法一种无视顶点的操作34Kruskal算法算法分析1、点无关的操作，只需要边结构，适合多点图,防止邻接阵暴内存。2、实现方便，代码清晰。3、O（VlogE）复杂度，稀疏图的良方！Kruskal算法算法分析35差分约束初步什么是差分约束？对于一组未知解[x1x2x3…xn-1xn]任意两个不同解xi,xj存在xi-xj>=(或<=)C（常数）,以此为模型构成的约束系统，称之为差分约束系统。差分约束初步36差分约束初步首先我们回顾下松弛技术，在Bellman-Ford算法中，有一个十分关键的三角不等式Dis[i]+w(i,j)<Dis[j]使得迭代结束后所有的Dis[j]<=Dis[i]+w(i,j)！！再结合差分约束系统的概念，任意未知数间存在xi-xj>=（或<=）C，我们取<=情况研究,则要求xi-xj<=C，即xi<=xj+C!!看出什么了么？对！这就是以j为始点，i为末点，C为权，构造出带约束边的图，并以此求得最短路径的算法啊！数与图得到了完美的结合！！差分约束初步首先我们回顾下松弛技术，在Bellman-For37最大流问题在带源点与汇点的带权连通网络G中，求得自源点出发，受各边容量限制最后到达汇点的流量的问题，称之为最大流问题。最大流网络满足3大性质：流守恒性网络内流不增加不减少容量限制流量受边负载限制反对称性任意结点流进多少流出多少解决方案：FF方法最大流问题在带源点与汇点的带权连通网络G中，求得自源点出发，38Ford-Fulkerson方法这是种方法而非算法，在此种方法指导下的算法最坏上界完全相同，但最好下界却各有千秋。增广路径：在残留网络中，从源点出发，可以通过该路径使得所经边残余流量减少，而通向汇点的流量增大。最小割-最大流定理：网络流中，存在的最大流受限制于该网络的最小割。E-K算法，此算法是最常用的最大流算法，以BFS为基础，每次选择残余网络中的结点数最少的可增广路径进行增广，直到无法进行下去，此算法的最大特点是最后一次保存的路径是该网络流的最小截集。Ford-Fulkerson方法这是种方法而非算法，在此种方39二分匹配对于图G，可以将顶点重构为两个集合，每个集合内的点不自交，则该图称之为二部图，对其求解最大匹配的过程称之为二分匹配。在普通二分匹配中，其最小路径覆盖为点数-最大匹配数。不带权二分匹配（匈牙利算法）带权二分匹配（KM算法）二分匹配对于图G，可以将顶点重构为两个集合，每个集合内的点不40匈牙利算法由匈牙利数学家提出的解决二分图匹配的算法。本质是找增广路径。这里的增广路径定义为交错轨，即一端为已匹配点，另一端为未匹配点，如果通过任意顶点的遍历，能够找到这样的路径，则对其取反,必会使匹配数+1，如此迭代直到无法找到这样的路径为止。对最大匹配的题目一般以最小路径覆盖的形式出现。匈牙利算法由匈牙利数学家提出的解决二分图匹配的算法。41KM算法KM算法是通过给每个顶点一个标号（叫做顶标）来把求最大权匹配的问题转化为求完备匹配的问题的。设顶点Xi的顶标为A[i]，顶点Yi的顶标为B[i]，顶点Xi与Yj之间的边权为w[i,j]。在算法执行过程中的任一时刻，对于任一条边(i,j)，A[i]+B[j]>=w[i,j]始终成立。KM算法的正确性基于以下定理： 若由二分图中所有满足A[i]+B[j]=w[i,j]的边(i,j)构成的子图（称做相等子图）有完备匹配，那么这个完备匹配就是二分图的最大权匹配。 这个定理是显然的。因为对于二分图的任意一个匹配，如果它包含于相等子图，那么它的边权和等于所有顶点的顶标和；如果它有的边不包含于相等子图，那么它的边权和小于所有顶点的顶标和。所以相等子图的完备匹配一定是二分图的最大权匹配。算法的本质是对匈牙利算法的改进，但实际上却比匈牙利算法早发表几年，其核心仍然是寻找增广路径的过程。KM算法KM算法是通过给每个顶点一个标号（叫做顶标）来把求42KM算法步骤初始时为了使A[i]+B[j]>=w[i,j]恒成立，令A[i]为所有与顶点Xi关联的边的最大权，B[j]=0。如果当前的相等子图没有完备匹配，就按下面的方法修改顶标以使扩大相等子图，直到相等子图具有完备匹配为止。我们求当前相等子图的完备匹配失败了，是因为对于某个X顶点，我们找不到一条从它出发的交错路。这时我们获得了一棵交错树，它的叶子结点全部是X顶点。现在我们把交错树中X顶点的顶标全都减小某个值d，Y顶点的顶标全都增加同一个值d，那么我们会发现：两端都在交错树中的边(i,j)，A[i]+B[j]的值没有变化。也就是说，它原来属于相等子图，现在仍属于相等子图。两端都不在交错树中的边(i,j)，A[i]和B[j]都没有变化。也就是说，它原来属于（或不属于）相等子图，现在仍属于（或不属于）相等子图。X端不在交错树中，Y端在交错树中的边(i,j)，它的A[i]+B[j]的值有所增大。它原来不属于相等子图，现在仍不属于相等子图。X端在交错树中，Y端不在交错树中的边(i,j)，它的A[i]+B[j]的值有所减小。也就说，它原来不属于相等子图，现在可能进入了相等子图，因而使相等子图得到了扩大。现在的问题就是求d值了。为了使A[i]+B[j]>=w[i,j]始终成立，且至少有一条边进入相等子图，d应该等于min{A[i]+B[j]-w[i,j]|Xi在交错树中，Yi不在交错树中}。理解原理就行，在一般情况下KM算法的代码不会调整，因此只要会使用模版，一切不在话下，当然图论本身就是充满了建模的思想，只有好的模型才能有真正的效率！KM算法步骤43KM算法效率O（V*V*V）KM算法的本质，对于N*N的矩阵每行每列只能取一个数，使其和为最大！！KM算法44强连通分支什么是强连通分支？强连通分支就是任意两点均可达的有向子图。理论：白色路径定理求解：Tarjan算法强连通分支什么是强连通分支？45强连通分支什么是时间戳？DFS进行时，访问到节点所花的时间算法理论依据：DFS时，如果所达的下一个点i已经被访问，则从该点j出发，寻找父节点到i，其间所经过的所有点必为以i为代表的强连通分支上的点(并查实现)如何判断是否是该次被访问？时间戳！强连通分支什么是时间戳？46强连通分支步骤对于每个顶点，设立Num、Low、Used、Alive四个属性，一个Stack保存当前正在被遍历的顶点；每访问一个顶点，将它的Num和Low设立为当前时间戳，Used、Alive设为True，并将顶点入栈；对于它的每条边，若边的终点未Used，则访问，而后用终点的Low值更新它的Low值，对于每个Used且Alive的终点，用它的Num值更新当前值；访问完毕当前顶点后，若Low与Num相等，说明找到了一个强连通分量，它包括栈中所有在当前顶点上方的顶点，将它们出栈并记下Belong值，出栈的顶点的Alive要置为false。扫描各点Belong值，其代表的点的个数便为强连通分支数！强连通分支步骤47强连通分支应用1、求解单纯问题HDU12692、缩图技术(适用于多点多边的关系闭包求解)强连通分支应用48待研究的问题次小生成树最优比例生成树最小树型图弦图稳定婚姻问题待研究的问题49数论

It’seasytolearn!数论

It’seasytolearn!50数论什么是数论？数论是研究整数性质的一门很古老的数学分支，其初等部分是以整数的整除性为中心的，包括整除性、不定方程、同余式、连分数、素数（即整数）分布以及数论函数等内容，统称初等数论（elementarynumbertheory）。初等数论的大部份内容早在古希腊欧几里德的《几何原本》中就已出现。欧几里得证明了素数有无穷多个，他还给出求两个自然数的最大公约数的方法，即所谓欧几里得算法。我国古代在数论方面亦有杰出之贡献，现在一般数论书中的「中国剩余定理」正是我国古代《孙子算经》中的下卷第26题，我国称之为「孙子定理」。近代初等数论的发展得益于费马、欧拉、拉格朗日、勒让德和高斯等人的工作。1801年，高斯的《算术探究》是数论的划时代杰作。高斯还提出：「数学是科学的皇后，数论是数学中的皇冠」。可见高斯对数论的高度评价。由于自20世纪以来引进了抽象数学和高等分析的巧妙工具，数论得到进一步的发展，从而开阔了新的研究领域，出现了代数数论、解析数论、几何数论等新分支。而且近年来初等数论在计算器科学、组合数学、密码学、代数编码、计算方法等领域内更得到了广泛的应用，无疑同时间促进着数论的发展。数论什么是数论？51同余定理对于正整数a,b,c(a%c+b%c)%c=(a+b)%c(a*b)%c=(a%c*b%c)%c注意对于除法与减法%运算为非封闭运算需要进行数论变换才能继续进行下去同余定理对于正整数a,b,c52同余定理大数求余设大数R=a1*10^0+a2*10^1+….+an*10^n-1则R%C=(a1*10^0%C+a2*10^1%C+….+an*10^n-1%C)%C可以在O（logn）时间内解决大数求余问题步骤：以字符读入大数后，设置计数器sum=0sum=(10*sum+key[i]-’0’)%C;迭代后令sum=sum%C;同余定理大数求余53GCDGCD（最大公约数）的一般求解欧几里德辗转相除法（必须掌握）If(a%b==0)returnb; Elsereturngcd(b,a%b); 本过程具有收敛性质……GCDGCD（最大公约数）的一般求解54扩展欧几里德在一些具体的题目中，我们还需要的到一组满足ax+by=gcd(a,b)的最小解，用以判断模方程是否有解，此时就要使用扩展欧几里德.相比一般欧几里德方法，扩展欧几里德有一个对于X，Y求解的递推过程。使用递归实现，递归条件为b==0时，X=1,Y=0;否则t=X;X=Y;Y=t-(a/b)*X;(递推求得)可以证明最后出来的X，Y必然是最小解.应用：模线性方程的求解扩展欧几里德在一些具体的题目中，我们还需要的到一组满足ax+55循环群生成元对于modn域中的任意数a，若有gcd(m,n)=1，则m为该域的生成元，使得a+km可以为域中任意数.证明十分简单，若gcd(m,n)=1，则lcm(m,n)=m*n,则对于a的modn运算,需要n次的计算才能回到a，期间必遍历该域中所有数！循环群生成元对于modn域中的任意数a，若有gcd(m,n56因子分解对于筛选大量数的因子分解工作，可以与筛选质数同时进行。令len[i]记录数i的因子个数，则对于每个素数p的倍数及本身，插入因子p，并使len值增长，筛选完所有素数后就完成了因子分解因子分解对于筛选大量数的因子分解工作，可以与筛选质数同时进行57素数判定对于一千万内素数的判定：筛选法最优对于一千万外素数的判定：米勒测试素数判定对于一千万内素数的判定：58筛选法给定辅助bool数组prime，首先全置true,使prime[0]=prime[1]=false;遍历，当遇到prime[i]=true,将之小于n的所有倍数置false；最后一次遍历，所有值为true的数即为素数！时空效率均摊相关伪线性复杂度筛选法给定辅助bool数组prime，首先全置true,使p59米勒测试理论基础——费马定理实践工具——二分求幂米勒测试60米勒测试费马定理：若p为素数----a^(p-1)%p==1注意此定理只为充分不为必要米勒测试以概率的形式避免了误判的发生从严格意义上来说米勒测试的意义并不科学但是实际证明在可数范围内的伪素数十分之少而且同时满足a=2,a=3,a=7的底的伪素数更是少得可怜，因此该测试从概率上满足了快速判定素数的需求。米勒测试费马定理：61米勒测试二分快速求幂模原理对于res=a^b%c的求解若b%2==0则res=((a^(b/2))%c*(a^(b/2))%c)%c否则res=(a*((a^(b/2))%c*(a^(b/2))%c))%c米勒测试二分快速求幂模原理62欧拉函数设E(n)为n以内（不包括n）与n互质数的个数，则E(n)称为关于n的欧拉函数。欧拉函数的求法，对于n=p1*p2*p3…pnE(n)=n*(1-1/p1)*(1-1/p2)…*(1-1/pn)可以以容斥原理证明其正确性！欧拉定理:a^(E(n))%n==1欧拉函数设E(n)为n以内（不包括n）与n互质数的个数，则E63模线性方程求解ax≡b(modn)有解，当且仅当b%gcd(a,n)==0使用扩展欧几里德求得d=gcd(a,n),则aX+nY=d,x=(X*(b/d))%nWhy?b/d=ma(X*m)+nY*m=b=>x=(X*m)%n模线性方程求解ax≡b(modn)有解，当且仅当b%gcd64中国剩余定理设n=n1*n2...nk,其中因子两两互质.有:a-----(a1,a2,...,ak),其中ai=amodni,则a和(a1,a2,...,ak),关系是一一对应的.就是说可以由a求出(a1,a2,...,ak),也可以由(a1,a2,...,ak)求出a求解：中国古代演算法模线性方程代入中国剩余定理设n=n1*n2...nk,其中因子两两互质65中国剩余定理应用大整数表示快速运算中国剩余定理应用66连分数逼近在数学中，连分数或繁分数即如上表达式.这里的a0是某个整数而所有其他的数an都是正整数。可依样定义出更长的表达式。如果部分分子（partialnumerator）和部分分母（partialdenominator）允许假定任意的值，在某些上下文中可以包含函数，则最终的表达式是广义连分数。在需要把上述标准形式与广义连分数相区别的时候，可称它为简单或正规连分数，或称为是规范形式的一个数的连分数表示是有限的，当且仅当这个数是有理数。“简单”有理数的连分数表示是简短的。任何有理数的连分数表示是唯一的，如果它没有尾随的1。（但是[a0;a1,...an,1]=[a0;a1,...an+1]。）无理数的连分数表示是唯一的。连分数的项将会重复，当且仅当它是一个二次无理数（即整数系数的二次方程的实数解）的连分数表示。数x的截断连分数表示很早产生x的在特定意义上“最佳可能”的有理数逼近。连分数逼近在数学中，连分数或繁分数即如上表达式.67连分数逼近意义1、精度保留2、避免浮点运算3、无理数的表示唯一4、研究连分数的动机源于想要有实数在“数学上纯粹”的表示。求解欧几里德变体！！连分数逼近意义68连分数逼近

连分数逼近69数据结构

Soul!!!数据结构

Soul!!!70数据结构什么是数据结构?数据结构是计算机存储、组织数据的方式。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率的算法。数据结构往往同高效的检索算法和索引技术有关。数据结构在计算机科学界至今没有标准的定义。个人根据各自的理解而有不同的表述方法：SartajSahni在他的《数据结构、算法与应用》一书中称：“数据结构是数据对象，以及存在于该对象的实例和组成实例的数据元素之间的各种联系。这些联系可以通过定义相关的函数来给出。”他将数据对象（dataobject）定义为“一个数据对象是实例或值的集合”。CliffordA.Shaffer在《数据结构与算法分析》一书中的定义是：“数据结构是ADT（抽象数据类型AbstractDataType）的物理实现。”LobertL.Kruse在《数据结构与程序设计》一书中，将一个数据结构的设计过程分成抽象层、数据结构层和实现层。其中，抽象层是指抽象数据类型层，它讨论数据的逻辑结构及其运算，数据结构层和实现层讨论一个数据结构的表示和在计算机内的存储细节以及运算的实现。数据结构什么是数据结构?71数据结构为什么要使用数据结构?1、便于理清结构，易于表示出一个实体的内部属性与外部联系。2、更好利用实体特性，从而为算法高效铺路。3、强有力的数据结构，能够取代算法的优势。数据结构为什么要使用数据结构?72数据结构数据结构的基本类型：1、顺序表2、链表3、广义表4、树5、图6、串数据结构数据结构的基本类型：73顺序表顺序表是在内存上开辟的连续片段，每个元素单元拥有固定大小，以此组织形成的数据结构。优点：1、随机存取2、索引唯一3、结构简单顺序表顺序表是在内存上开辟的连续片段，每个元素单元拥有固定大74顺序表一般应用：1、寄存数组（包括栈和队列）2、哈希数组3、树状数组顺序表一般应用：75寄存数组这是我们最常见的顺序表表现方式，一般的大数据量程序，如果不能有边读边处理的方法，就需要首先保留所有的输入，从而能够在而后的过程中进行处理。主要应用：1、各类算法的线性预处理2、保留线性逻辑关系3、记忆化辅助寄存数组这是我们最常见的顺序表表现方式，一般的大数据量程序，76寄存数组优点：1、静态2、随机3、高效缺点：1、插入与删除操作效率极度低下2、内存分配不灵活技巧：1、满足递推与DP内存需求滚动数组2、满足图的快速判重化行为数状态压缩寄存数组优点：77哈希数组什么是哈希？从广义上说哈希是一种键值对应的操作，是从数域到值域的一一映射，也就是我们通常称其为哈希函数的由来。为什么哈希表可以用数组实现？数组满足哈希的3个必要条件：1、键——index2、值——value3、键值映射（index->value）O（1）哈希数组什么是哈希？78哈希数组散列函数的选用一般情况下我们使用哈希数组，采用的是开放散列策略，也就是说内存与键是一一对应，即hash[key]=value,在对于key值要求不大的情况下是很好的选择。然而当要求的key很大时该怎么办，此时就应该选用一个好的映射函数使hash[f(key)]=value，且f(key)的值必定均匀分布在映射区间内。当然要找到这样的函数是十分困难的，我们无法了解到数据的具体信息，因此一般的f(key)为key%p，p为一个质数，结合数论知识，我们可以知道当gcd(key,p)=1时，key是一个循环群生成元，使用这个性质，我们可以少了许多因大多数冲突而引发避免策略造成的效率问题。哈希数组散列函数的选用79哈希数组HDU2192题意：递增的序列组成一个集合请问至少有几个？思路？哈希数组HDU219280哈希数组出现次数最多的数，决定了能分成的最少群落！实现方式？？哈希！！！散列函数——如何刻画？思考！根据问题的输入规模，最大10^4个数，因此选取大于10^4的质数作为散列函数的参数，令f(key)=key%p还有什么问题？思考出现冲突！！！！哈希数组出现次数最多的数，决定了能分成的最少群落！81哈希数组解决方案：1、线性扫描法2、二次线性扫描3、桶链问题完美解决，注意各个结点在不同解决方案下添加的相关变量。哈希数组解决方案：82树状数组首先我们得知道一个问题,那就是线段树的作用并不只是用来存储线段的,也可以存储点的值等等.对于静态的线段树,空间上需要的数组有:当前结点的数据值,左儿子编号,右儿子编号.至少这么三个数组.而在时间上虽然是NlogN的复杂度,但是系数很大.实现起来的时候编程复杂度大,空间复杂度大,时间效率也不是很理想.树状数组首先我们得知道一个问题,那就是线段树的作用并不只是用83有!那就是树状数组!那么是否有更好的解决方法呢?有!那就是树状数组!那么是否有更好的解决方法呢?84树状数组先看一个例题:数列操作:给定一个初始值都为0的序列,动态地修改一些位置上的数字,加上一个数,减去一个数,或者乘上一个数,然后动态地提出问题,问题的形式是求出一段数字的和.树状数组先看一个例题:85树状数组如果直接做的话,修改的复杂度是O(1),询问的复杂度是O(N),M次询问的复杂度是M*N.M,N的范围可以有100000以上树状数组如果直接做的话,修改的复杂度是O(1),询问的复杂度86用线段树可以这样解:若要维护的序列范围是0..5,先构造下面的一棵线段树:用线段树可以这样解:若要维护的序列范围是0..5,先构造下面87树状数组可以看出,这棵树的构造用二分便可以实现.复杂度是2*N.每个结点用数组a来表示该结点所表示范围内的数据之和.修改一个位置上数字的值,就是修改一个叶子结点的值,而当程序由叶子结点返回根节点的同时顺便修改掉路径上的结点的a数组的值.对于询问的回答,可以直接查找i..j范围内的值,遇到分叉时就兵分两路,最后在合起来.也可以先找出0..i-1的值和0..j的值,两个值减一减就行了.后者的实际操作次数比前者小一些.这样修改与维护的复杂度是logN.询问的复杂度也是logN,对于M次询问,复杂度是MlogN.树状数组可以看出,这棵树的构造用二分便可以实现.复杂度是2*88树状数组用树状数组!!!然而不难发现,线段树的编程复杂度大,空间复杂度大,时间效率也不高.怎么办树状数组用树状数组!!!然而不难发现,线段树的编程复杂度大,89树状数组下图中的C数组就是树状数组,a数组是原数组先自己研究一下这个东西

树状数组下图中的C数组就是树状数组,a数组是原数组先自己研究90树状数组可以发现这些规律C1=a1C2=a1+a2C3=a3C4=a1+a2+a3+a4C5=a5……C8=a1+a2+a3+a4+a5+a6+a7+a8……C2^n=a1+a2+….+a2^n树状数组可以发现这些规律91树状数组对于序列a，我们设一个数组C定义C[i]=a[i–2^k+1]+…+a[i]，k为i在二进制下末尾0的个数。K的计算可以这样:2^k=xand(xxor(x-1))以6为例(6)10=(0110)2xor6-1=(5)10=(0101)2(0011)2and(6)10=(0110)2(0010)2树状数组对于序列a，我们设一个数组C定义C[i]=a[i92树状数组functionLowbit(x:Integer):Integer;beginLowbit:=xand(xxor(x–1));end;若要修改a[i]的值,则C数组的修改是:Procedurechange(k,delta:integer);Beginwhilek<=ndobeginC[k]:=C[k]+delta;k:=k+lowbit(k);End;End;树状数组functionLowbit(x:Integer93树状数组若要求I..j的元素和的值,则求出1..I-1的值和1..j的值.Functiongetsum(k:integer):integer;Vart:integer;Begint:=0;whilek>0dobegint:=t+c[k];k:=k-lowbit(k);end;getsum:=t;End;树状数组若要求I..j的元素和的值,则求出94树状数组对于刚才的一题,每次修改与询问都是对C数组做处理.空间复杂度有3N降为N,时间效率也有所提高.编程复杂度更是降了不少.在很多的情况下,线段树都可以用树状数组实现.凡是能用树状数组的一定能用线段树.当题目不满足减法原则的时候,就只能用线段树,不能用树状数组.例如数列操作如果让我们求出一段数字中最大或者最小的数字,就不能用树状数组了.树状数组对于刚才的一题,每次修改与询问都是对C数组做处理.空95链表链表是内存中不连续块链接而成的数据结构，本着使用多少分配多少的原则，极大地节约和利用了内存，是一种十分基础的数据结构。优势：1、动态分配2、快速删除与插入3、节省空间链表链表是内存中不连续块链接而成的数据结构，本着使用多少分配96链表缺点：1、查找效率低下2、动态分配结点调用操作系统实现，导致空间分配效率消耗一种对空间的优化：内存静态化！！一般应用1、桶2、跳跃表链表缺点：97桶一般用做哈希的冲突避免策略，使用桶结构存储在同一冲突域下的数据，作为键值的扩展。基数数排序的辅助结构。桶一般用做哈希的冲突避免策略，使用桶结构存储在同一冲突域下的98跳跃表可以看做是链表结构最优秀的应用，使用跳跃表有着令人震撼的效率，对查询、删除和添加的操作均为O（logn）的复杂度。利用了链表自身的特点，以较小的空间代价提升了自身的性能。使用了概率算法，使效率堪与AVL、RB-Tree等BST相媲美。相比而言，极低的编程复杂度！！！有什么理由可以不去掌握呢？跳跃表可以看做是链表结构最优秀的应用，使用跳跃表有着令人震撼99跳跃表跳跃表由多条链构成（S0，S1，S2……，Sh），且满足如下三个条件：每条链必须包含两个特殊元素：+∞和-∞S0包含所有的元素，并且所有链中的元素按照升序排列。每条链中的元素集合必须包含于序数较小的链的元素集合，即：535353454537303030291511111111-∞-∞-∞-∞+∞+∞+∞+∞S0S1S2S3跳跃表的实例跳跃表跳跃表由多条链构成（S0，S1，S2……，Sh），且100跳跃表之查找目的：在跳跃表中查找一个元素x 在跳跃表中查找一个元素x，按照如下几个步骤进行：从最上层的链（Sh）的开头开始假设当前位置为p，它向右指向的节点为q（p与q不一定相邻），且q的值为y。将y与x作比较x=y 输出查询成功，输出相关信息x>y 从p向右移动到q的位置x<y 从p向下移动一格如果当前位置在最底层的链中（S0），且还要往下移动的话，则输出查询失败535353454537303030291511111111-∞-∞-∞-∞+∞+∞+∞+∞查询元素53的全过程S0S1S2S3查找成功！跳跃表之查找目的：在跳跃表中查找一个元素x5353101跳跃表之插入目的：在跳跃表中插入一个元素x插入操作由两部分组成：查找插入的位置和插入对应元素。为了确定插入的“列高”，我们引入一个随机决策模块：产生一个0到1的随机数r r←random()如果r小于一个概率因子P，则执行方案A， ifr<p thendoA否则，执行方案B elsedoB列的初始高度为1。插入元素时，不停地执行随机决策模块。如果要求执行的是A操作，则将列的高度加1，并且继续反复执行随机决策模块。直到第i次，模块要求执行的是B操作，我们结束决策，并向跳跃表中插入一个高度为i的列。跳跃表之插入目的：在跳跃表中插入一个元素x列的初始高度为1102跳跃表之插入假设我们现在要插入一个元素40到已有的跳跃表中。373030302915-∞-∞-∞-∞S0S1S2S3插入的位置5353534545+∞+∞+∞+∞40404040高度+1随机化模块运行状况：高度=4高度+1高度+1结束53跳跃表之插入假设我们现在要插入一个元素40到已有的跳跃表中。103跳跃表之删除 目的：从跳跃表中删除一个元素x删除操作分为以下三个步骤：在跳跃表中查找到这个元素的位置，如果未找到，则退出将该元素所在整列从表中删除将多余的“空链”删除 -∞-∞-∞-∞S0S1S2S3111111115353534545373030302915+∞+∞+∞+∞5353534545373030302915-∞-∞-∞+∞+∞+∞S0S1S2跳跃表之删除 目的：从跳跃表中删除一个元素x-∞-∞104跳跃表之概率因子影响在插入操作中，我们引入了一个概率因子P，它决定了跳跃表的高度，并影响到了整个数据结构的效率。让我们来看看在实际评测过程中，不同的P在时空效率上的差异。P平均操作时间平均列高总结点数每次查找跳跃次数（平均值）每次插入跳跃次数（平均值）每次删除跳跃次数（平均值）2/30.0024690ms3.0049123339.87841.60441.5661/20.0020180ms1.9956068327.80729.94729.0721/e0.0019870ms1.5844757027.33228.23828.4521/40.0021720ms1.3304047828.72629.47229.6641/80.0026880ms1.1443442035.14735.82136.007跳跃表之概率因子影响在插入操作中，我们引入了一个概率因子P，105跳跃表高效率的相关操作和较低的编程复杂度使得跳跃表在实际应用中的范围十分广泛。尤其在那些编程时间特别紧张的情况下，高性价比的跳跃表很可能会成为你的得力助手。在实际编程中，使用指针而非构造多级链表以实现跳跃。跳跃表高效率的相关操作和较低的编程复杂度使得跳跃表在实际应用106广义表广义表是对表概念的扩充，使链表到树之间的概念缓冲，其所有的表元素并非原子集合，在概念上是对自身的递归定义。实际应用：Trie广义表广义表是对表概念的扩充，使链表到树之间的概念缓冲，其所107Trie什么是Trie?Trie是一种十分清晰的广义表结构，它存储字母，并实现了前缀字母路径唯一，因此被称作前缀字典树，或者字母树。它是如何实现的呢？Trie什么是Trie?108Trie前缀共享每个结点分叉26条支路实现跳转以标记变量表示一个单词的结束其中前缀共享是一个非常重要的性质！！Trie前缀共享109TrieHDU1251题意：中文题！！自己理解!!思考？。。。TrieHDU1251110Trie根据题意，需要统计单词前缀，此时，首先应将所有字典单词加入Trie。在加入的过程中，在各结点设置计数器，每个字母走过后，进行计数累加。得到查询串，在字典树上走完后，返回计数器值。是不是很简单？Trie根据题意，需要统计单词前缀，此时，首先应将所有字典单111树树的实质就是对广义表的约束，它只有一个入度为0的结点，作为一切遍历的开始，这也是对非线性数据结构的一种形象表示。优点：1、快速查找2、快速删除与插入3、内存分配的灵活总结：可见树是对链表与数组优势的互补，缺憾的折衷，可以说是一种优秀的数据结构。树树的实质就是对广义表的约束，它只有一个入度为0的结点，作为112树树结构的一些应用：1、二叉排序树2、二叉平衡树3、堆4、可并堆5、AC自动机树树结构的一些应用：113二叉排序树所谓二叉排序树是这样的一种结构，对于它的每个结点，左儿子的值小于根的值，右儿子的值大于根值，对其进行中序遍历后，将得到一个递增的数列。优点：1、适用于快速查找2、实现简单二叉排序树所谓二叉排序树是这样的一种结构，对于它的每个结点，114二叉排序树缺点只有一个：树的退化（致命的）怎么样才算是一种退化？思考！以降序输入数据后，得到的将是一张链表，查找效率退化为O(n)二叉排序树缺点只有一个：115二叉排序树如何解决？引入平衡概念！！BST从此诞生！！二叉排序树116二叉平衡树什么是二叉平衡树？任意结点左子树深度与右子树深度之差的绝对值不大于1如何保持这一性质？AVL：记录深度，违反平衡必引起旋转。RB-Tree:进行染色，违反染色原则，进行重染，不超过3次的旋转染色。实际上STL都已经封装了这2个数据结构AVL（BinarySearchTree），RB-Tree(SetorMap)!二叉平衡树什么是二叉平衡树？117堆以树为概念，以树型数组实现的数据结构满足对于任意结点，其值必然小于左儿子与右儿子的值理论证明，从堆中得到最小元素的复杂度是log(n),因此为n个序列进行排序的复杂为nlog(n)。其构造复杂度不超过O（4n），在小数据量下甚至超过了主算法，因此在数据较小情况下不考虑使用堆排序。STL的封装priority_queue!!堆以树为概念，以树型数组实现的数据结构118堆性质对于堆来说，堆顶永远为堆中最小值。每次pop，将牺牲O(logn)的时间进行调整每次push，将牺牲O(logn)的时间进行调整致命缺陷：堆的归并！！！思考，为什么？2个大小为n的堆进行归并，必须逐个弹入，即O(nlogn)的复杂度，不可进行快速归并，否则将影响堆的平衡性！如何解决？堆性质119可并堆为了解决堆间的合并问题，必须使用一个更好的数据结构适应这种频繁的操作。目前有2种编程复杂度比较实际的应用1、左偏树2、斜堆可并堆为了解决堆间的合并问题，必须使用一个更好的数据结构适应120左偏树一个左偏树满足如下性质：1、左偏树(LeftistTree)是一种可并堆(MergeableHeap)，它除了支持优先队列的三个基本操作（插入，删除，取最小节点），还支持一个很特殊的操作——合并操作2、左偏树是一棵堆有序(HeapOrdered)二叉树。3、左偏树满足左偏性质(LeftistProperty)。左偏树一个左偏树满足如下性质：121左偏树的性质定义一棵左偏树中的外节点(ExternalNode)为左子树或右子树为空的节点。定义节点i的距离(dist(i))为节点i到它的后代中，最近的外节点所经过的边数。任意节点的左子节点的距离不小于右子节点的距离（左偏性质）左偏树满足下面两条基本性质：[性质1]节点的键值小于或等于它的左右子节点的键值。即key(i)≤key(parent(i))这条性质又叫堆性质。符合该性质的树是堆有序的(Heap-Ordered)。有了性质1，我们可以知道左偏树的根节点是整棵树的最小节点，于是我们可以在O(1)的时间内完成取最小节点操作。[性质2]节点的左子节点的距离不小于右子节点的距离。即dist(left(i))≥dist(right(i))这条性质称为左偏性质。性质2是为了使我们可以以更小的代价在优先队列的其它两个基本操作（插入节点、删除最小节点）进行后维持堆性质。。由左偏性质可知，一个节点的距离等于以该节点为根的子树最右路径的长度。定理：若一棵左偏树有N个节点，则该左偏树的距离不超过

log(N+1)

-1。左偏树的性质定义一棵左偏树中的外节点(ExternalNo122左偏树C←Merge(A,B)Merge()把A,B两棵左偏树合并，返回一棵新的左偏树C，包含A和B中的所有元素。在本文中，一棵左偏树用它的根节点的指针表示。在合并操作中，最简单的情况是其中一棵树为空（也就是，该树根节点指针为NULL）。这时我们只须要返回另一棵树。若A和B都非空，我们假设A的根节点小于等于B的根节点（否则交换A,B），把A的根节点作为新树C的根节点，剩下的事就是合并A的右子树right(A)和B了。right(A)←Merge(right(A),B)合并了right(A)和B之后，right(A)的距离可能会变大，当right(A)的距离大于left(A)的距离时，左偏树的性质2会被破坏。在这种情况下，我们只须要交换left(A)和right(A)。若dist(left(A))>dist(right(A))，交换left(A)和right(A)

最后，由于right(A)的距离可能发生改变，我们必须更新A的距离：dist(A)←dist(right(A))+1不难验证，经这样合并后的树C符合性质1和性质2，因此是一棵左偏树。至此左偏树的合并就完成了。左偏树C←Merge(A,B)123左偏树合并操作都是一直沿着两棵左偏树的最右路径进行的。一棵N个节点的左偏树，最右路径上最多有

log(N+1)

个节点。因此，合并操作的时间复杂度为：

O(logN1+logN2)=O(logN)合并操作的代码如下： FunctionMerge(A,B) IfA=NULLThenreturnB IfB=NULLThenreturnA Ifkey(B)<key(A)Thenswap(A,B) right(A)←Merge(right(A),B) Ifdist(right(A))>dist(left(A))Then swap(left(A),right(A)) Ifright(A)=NULLThendist(A)←0 Elsedist(A)←dist(right(A))+1 returnA EndFunction左偏树合并操作都是一直沿着两棵左偏树的最右路径进行的。124左偏树左偏树的特点：时空效率高编程复杂度低左偏树的应用：可并堆优先队列左偏树左偏树的特点：125左偏树HDU1512题意：刚开始所有的猴子自成一群且互相都不认识，他们互相认识当且仅当他们各自群中最强的猴子互相打了一场，体力各减为一半。问最后这群猴子中体力最强猴子的体力是多少思路如何？左偏树HDU1512126左偏树并查？可行，但只能作为辅助手段。优先队列+并查？O（nlogn）的合并效率实在不敢恭维很好。。。左偏树开始发挥了效力了！左偏树并查？127左偏树步骤：使用并查集（这里其实准确来说应该是一种记录父结点编号的数组）记录各结点在各自堆中的父结点查询两只猴子所在堆的根结点，如果两只猴子根结点相同，则不必打架，否则，取各自堆中最大元素（也就是根结点）打一场打架，此时先让各自堆中根的左右儿子指向本身，再对左右儿子进行合并生成新树（即pop操作）并适当修改父结点数组，令根结点值减半后与新树再次合并，并适时修改父结点数组（即push操作），再将两个堆中的根进行合并（即unition操作）。是不是很简单的实现？左偏树步骤：128斜堆如何对左偏树进行优化？思考！！！我们注意到在左偏树中必须要有距离的概念，但我们可以发现一个性质，如果每次合并都向右进行，每次完成后将右边的结点甩到左边，不正好符合了左偏的性质么？很好去掉距离，提高效率，优化的王道！不足（单次合并可能退化到O(n)，但实际效果上，两者都差不多）斜堆如何对左偏树进行优化？129AC自动机AC自动机是由Aho和Corasick提出的数据结构,是对Trie树的一种改造，是对find操作的修正，也是多模式串匹配的基本实现！HDU2222题意给你N个关键字,以及一句描述,问有多少个关键字在这句描述中出现?思路???AC自动机AC自动机是由Aho和Corasick提出的数据结130AC自动机采用普通方法？O（Nnm）…m=50,n=1000000,N=10000黄花菜都凉了……KMP?O(N(m+n))?就这点优化？塞牙缝都不够那怎么办！！！AC自动机！！O（Nm+n）…强大！！！AC自动机采用普通方法？131AC自动机步骤将所有关键字塞入Trie好了，现在我们已经有一棵Trie了，但这还不够，我们还要在Trie上引入一个很强大的东西：失败指针或者说shift数组或者说Next函数…..你爱怎么叫怎么叫吧，反正就是KMP的精华所在，这也是我为什么叫你看KMP的原因。KMP中我们用两个指针i和j分别表示，A[i-j+1..i]与B[1..j]完全相等。也就是说，i是不断增加的，随着i的增加j相应地变化，且j满足以A[i]结尾的长度为j的字符串正好匹配B串的前j个字符，当A[i+1]<>B[j+1]，KMP的策略是调整j的位置（减小j值）使得A[i-j+1..i]与B[1..j]保持匹配且新的B[j+1]恰好与A[i+1]匹配（从而使得i和j能继续增加）。Trie树上的失败指针与此类似。AC自动机步骤132AC自动机假设有一个节点k，他的失败指针指向j。那么k,j满足这个性质：设root到j的距离为n，则从k之上的第n个节点到k所组成的长度为n的单词，与从root到j所组成的单词相同。那么我们要怎样构建这个东西呢？其实我们可以用一个简单的BFS搞定这一切。对于每个节点，我们可以这样处理：设这个节点上的字母为C，沿着他父亲的失败指针走，直到走到一个节点，他的儿子中也有字母为C的节点。然后把当前节点的失败指针指向那个字目也为C的儿子。如果一直走到了root都没找到，那就把失败指针指向root最开始，我们把root加入队列(root的失败指针显然指向自己)，这以后我们每处理一个点，就把它的所有儿子加入队列，直到搞完。好了，现在我们有了一棵带失败指针的Trie了！！！可以开始进行AC自动机了！AC自动机假设有一个节点k，他的失败指针指向j。那么k,j满133AC自动机一开始，Trie中有一个指针t1指向root，待匹配串(也就是“文章”)中有一个指针t2指向串头。接下来的操作和KMP很相似：如果t2指向的字母，是Trie树中，t1指向的节点的儿子，那么t2+1,t1改为那个儿子的编号，否则t1顺这当前节点的失败指针向上找，直到t2是t1的一个儿子，或者t1指向根。如果t1路过了一个绿色的点，那么以这个点结尾的单词就算出现过了。或者如果t1所在的点可以顺着失败指针走到一个绿色点，那么以那个绿点结尾的单词就算出现过了。本题要注意的是必须在描述串后面添加特殊符号，否则将忽略对完全匹配关键字的统计。注意：BFS寻找失败指针的过程，是一个自我匹配的过程。AC自动机一开始，Trie中有一个指针t1指向root，待匹134AC自动机特点：多模式匹配的良方，一次自我适配后，对任意文章的匹配均是线性复杂度。编程复杂度较低。使用方便，居家旅行之必备！AC自动机特点：135图图的结构是树结构的拓展，但在实现基本以数组的形式进行，在本质上来说所有的数据结构都是互相渗透交融的，所谓大道行简，只有掌握了本质，才能以不变应万变！！！基本表示：邻接阵邻接表由于上部分内容已经有所涉猎，这里就不再提过了图图的结构是树结构的拓展，但在实现基本以数组的形式进行，在本136串什么是串？串是由字符所组成的有限序列，我们只关心串的字符属性，而不关心其数值属性。串有着十分明显的逻辑结构，前驱后继都是固定的，不得随意更改！关于字符串的处理一般而言都是ICPC的中档题目，如果使用模拟或者暴力方法，一般来说都是无效的。应用结构：后缀数组串什么是串？137后缀数组什么是后缀数组？对于长度为len的字符串str，从位置i开始至len的所有字符序列称为i的后缀后缀数组（SA）保存的就是这些后缀序列的排序后的开头位置.Rank数组是SA的反函数，也就是说Rank[i]保存的是从位置i开始的后缀在所有后缀中的名次.后缀数组什么是后缀数组？138后缀数组如何利用这种结构性质？我们还需要计算一个辅助的工具——最长公共前缀（LongestCommonPrefix）!!对两个字符串u,v定义函数lcp(u,v)=max{i|u=iv}，也就是从头开始顺次比较u和v的对应字符，对应字符持续相等的最大位置，称为这两个字符串的最长公共前缀。对正整数i,j定义LCP(i,j)=lcp(Suffix(SA[i]),Suffix(SA[j])，其中i,j均为1至n的整数。LCP(i,j)也就是后缀数组中第i个和第j个后缀的最长公共前缀的长度。关于LCP有两个显而易见的性质：性质2.1LCP(i,j)=LCP(j,i)性质2.2LCP(i,i)=len(Suffix(SA[i]))=n-SA[i]+1这两个性质的用处在于，我们计算LCP(i,j)时只需要考虑i<j的情况，因为i>j时可交换i,j，i=j时可以直接输出结果n-SA[i]+1。后缀数组如何利用这种结构性质？139后缀数组直接根据定义，用顺次比较对应字符的方法来计算LCP(i,j)显然是很低效的，时间复杂度为O(n)，所以我们必须进行适当的预处理以降低每次计算LCP的复杂度。经过仔细分析，我们发现LCP函数有一个非常好的性