Skip to content

Tag Archives: 算法

字符串匹配自动机

首先(不严谨地)定义自动机:自动机就是一堆状态的组合,给某个状态的自动机一个输入,它会按照自己的转移规则变到一个新的状态。事实上,可以把状态理解成顶点,把状态的转移理解成上面标着符号的边,在某个状态得到了某个符号的输入时,就转移到那条边指向的状态去。 先介绍单串匹配的自动机。对于M个字符的串S[1..M],一个用这个串进行模式匹配的自动机需要M+1个状态。设状态i输入ch时的转移为auto[i][ch]。状态转移时要满足:若当前在状态i,说明已输入的最后i个字符是S[1..i],若有多个状态满足这个定义,则应该在编号最大的状态。如何保证上述条件始终被满足呢?首先,auto[i][S[i+1]]=i+1,这是明显的。如果ch!=S[i+1],则auto[i][ch]肯定应该转移到某个小于等于i的状态,这个状态j应该满足:它是串S[1..j]是S[1..i]+ch的后缀,且j是最大的。找出j的方法是:计算每个i的“后缀状态”,也就是给自动机输入S[2..i]后自动机应该在的状态suffix[i],则当输入ch时应该转移的状态就是auto[suffix[i]][ch]的转移。计算suffix的方法是:suffix[i+1]=auto[suffix[i]][S[i+1]],suffix[1]=0。单字符串的自动机就是这样构造的。每次转移到状态M时,就找到了一个匹配。 值得注意的是,上述suffix数组所含的信息和KMP算法求出的所谓next数组其实是完全一致的。其实CLRS上也说,KMP算法就是通过少量的预处理实时地均摊O(1)地求出自动机的状态转移(大意)。也就是说,串匹配自动机也可以这样实现:首先通过预处理求出suffix数组,然后在状态i输入了字符ch时,需要转移到状态auto[i][ch],但是具体转移到哪个状态我们并没有预处理求出,我们只知道:若S[i+1]==ch则转移到i+1,否则转移到auto[suffix[i]][ch]。利用这两个条件,前者可以看做递归边界,就可以递归的求出每个需要的转移。可以证明的是这种求的复杂度是均摊O(1)的。 然后来看多字符串匹配的情况,其实和单字符串的时候差别不大,只不过状态之间不再是一个简单的线性结构了,而是一个Trie的结构,要根据刚才那个“后缀状态”的定义求出所有没有在Trie中直接出现的边应该转移到什么地方,同样也可以像KMP算法实时地计算那些转移。具体的方法都跟单串的没什么差别。 SPOJ上有两道题可以练习自动机:PSTRING是利用单串匹配自动机(或者KMP)进行状态转移的DP,WPUZZLES则是直接的多串自动机应用。 关于字符串匹配自动机,更详细的说明和更多应用可以找Maigo(王赟)关于Trie图的论文。

构造Suffix Array的DC3算法

Suffix Array这个东西的确非常有用,很多关于字符串处理的题目构造一个SA就能迎刃而解。最近在SPOJ上看到了题目SUBST1,一眼看出来是用SA解的,兴冲冲的写了个nlogn的算法,连测试数据都没有出就交上去,结果没有悬念的TLE了(按说n=50000时nlogn算法应该可以不TLE的,比如说给50000个数排序肯定就不会TLE,可见SA的常数之大)……于是没办法,只好开始学SA的线性算法。 找到了这篇论文,似乎就是大家所说的三分法的“Skew Algorithm”的原始出处。作者在文章里说这种算法的基本原理是“Difference Cover”原则,并且在采样(Sample)的时候以3为模,所以这个算法叫DC3(Difference Cover modulo 3)。在本文里这个算法的名字就以原始论文为准了。 DC3算法的基本过程是这样的:首先构造出来一个superstring,这个串的每个字母都是原串的字母拼接上后面的两个字母,但这个串仅包含原串中下标模3不为0的位置。(递归地)求出这个串的SA,设为SA12。显然SA12中串的排列顺序与最终结果SA的排列顺序是相同的,只是SA12包含的串只有原串的2/3。 然后利用这个SA12和原串在线性时间内求出没有包含在SA12中的1/3的串的SA(也就是下标模3为0的那些串),设为SA0。求SA0的方法是:串的初始顺序是它们后面那个串在SA12中的顺序,然后再依据第一个字母进行一次RadixSort就可以了。也就是说SA0中的顺序可以仅用两个关键字来确定:第一关键字是第一个字母,第二关键字是后面的那个串在SA12中的位置。 现在得到了SA0和SA12,只需要把它们合并就可以得到最终的SA了,要想在线性时间内完成合并,需要在常数时间内完成比较。其实也不太难:当模为0的一个串与模为1的一个串比较时,需要比较它们的第一个字母与它们后面的那个串(都在SA12中),当模为0的一个串与模为2的一个串比较时,需要比较它们的前两个字母与它们去掉前两个字母以后的那个串(显然也都在SA12中)。 具体实现有点麻烦,我目前的代码基本上是完全抄的论文后面给的C++程序。不过运行速度真的很理想。因为程序里有一个很强的优化:当superstring中所有的字符都不相同时,可以直接用一遍RadixSort得到SA12,不用递归。经过这样的优化,递归地层数非常少,对于完全随机生成的长度为50000的英文字符串,求一次SA平均只需进行4次调用。所以实际时间效率非常高,常数不算大。 目前我对这个算法的理解还远不够深刻,所以讲的可能不易理解。有能力的话就看上面给出的原始论文吧,只看前三节就可以,后面讲了如何以牺牲一定时间为代价优化空间使用,我们是完全用不着的。 实例代码见上面的论文的附录A吧,我写得跟那个一样。

最小树形图

最小树形图就是给定一个有向图,求以某个给定顶点为根的有向生成树(也就是说沿着这N-1条有向边可以从根走到任意点),使权和最小。 解决这个问题有一个O(VE)的算法,是这样的:对于除根外的每个顶点,选择一条权最小的入边。如果选出来的V-1条边不构成环,则可以证明这些边就是满足要求的答案。如果存在环,则将环中的边收缩成一个顶点。设x是环中的点,y不是环中的点,v为新的顶点,w0为上一步中x选择的入边的权值,则原来的权值为w的边(x,y)变成权值为w的边(v,y),原来的权值为w的边(y,x)变成权值为w-w0的边(y,v)。这时最小树形图的答案就是环的权值和加上收缩以后的图的答案。 为什么收缩了以后要减小权值呢?很简单,最小树形图需要每个顶点选一条入边,顶点x当前已经有入边了,如果以后再给收缩后的顶点x选择权值为w的(原来属于x的)入边,就意味着已经选择的那条权值为w0的入边可以去掉了,也就是说选择这条边的代价应该是w-w0,所以就做这样的修改。 不过如果不固定根,我还不太知道如何用同样的复杂度解决,谁写过请教教我。 (发现自己最近表达能力很差,这个文章说得清楚些。) 示例程序(TJU2248,用邻接矩阵写的,O(V^3),比较简洁): tju2248.cpp

求最大权二分匹配的KM算法

最大权二分匹配问题就是给二分图的每条边一个权值,选择若干不相交的边,得到的总权值最大。解决这个问题可以用KM算法。理解KM算法需要首先理解“可行顶标”的概念。可行顶标是指关于二分图两边的每个点的一个值lx[i]或ly[j],保证对于每条边w[i][j]都有lx[i]+ly[j]-w[i][j]>=0。如果所有满足lx[i]+ly[j]==w[i][j]的边组成的导出子图中存在一个完美匹配,那么这个完美匹配肯定就是原图中的最大权匹配。理由很简单:这个匹配的权值之和恰等于所有顶标的和,由于上面的那个不等式,另外的任何匹配方案的权值和都不会大于所有顶标的和。 但问题是,对于当前的顶标的导出子图并不一定存在完美匹配。这时,可以用某种方法对顶标进行调整。调整的方法是:根据最后一次不成功的寻找交错路的DFS,取所有i被访问到而j没被访问到的边(i,j)的lx[i]+ly[j]-w[i][j]的最小值d。将交错树中的所有左端点的顶标减小d,右端点的顶标增加d。经过这样的调整以后:原本在导出子图里面的边,两边的顶标都变了,不等式的等号仍然成立,仍然在导出子图里面;原本不在导出子图里面的边,它的左端点的顶标减小了,右端点的顶标没有变,而且由于d的定义,不等式仍然成立,所以他就可能进入了导出子图里。 初始时随便指定一个可行顶标,比如说lx[i]=max{w[i][j]|j是右边的点},ly[i]=0。然后对每个顶点进行类似Hungary算法的find过程,如果某次find没有成功,则按照这次find访问到的点对可行顶标进行上述调整。这样就可以逐步找到完美匹配了。 值得注意的一点是,按照上述d的定义去求d的话需要O(N^2)的时间,因为d需要被求O(N^2)次,这就成了算法的瓶颈。可以这样优化:设slack[j]表示右边的点j的所有不在导出子图的边对应的lx[i]+ly[j]-w[i][j]的最小值,在find过程中,若某条边不在导出子图中就用它对相应的slack值进行更新。然后求d只要用O(N)的时间找到slack中的最小值就可以了。 如果是求最小权匹配,只需要把那个不等式反一下就行了。算法需要作出的改变是:lx的初值为所有临界边中的最小值,find中t反号。 示例程序(Ural 1076): ural1076.cpp

求最大流的Relabel-to-Front算法

除了用各种方法在剩余网络中不断找增广路(augmenting)的Ford-Fulkerson系的算法外,还有一种求最大流的算法被称为压入与重标记(Push-Relabel)算法。它的基本操作有:压入,作用于一条边,将边的始点的预流尽可能多的压向终点;重标记,作用于一个点,将它的高度(也就是label)设为所有邻接点的高度的最小值加一。Push-Relabel系的算法普遍要比Ford-Fulkerson系的算法快,但是缺点是相对难以理解。 Relabel-to-Front使用一个链表保存溢出顶点,用Discharge操作不断使溢出顶点不再溢出。Discharge的操作过程是:若找不到可被压入的临边,则重标记,否则对临边压入,直至点不再溢出。算法的主过程是:首先将源点出发的所有边充满,然后将除源和汇外的所有顶点保存在一个链表里,从链表头开始进行Discharge,如果完成后顶点的高度有所增加,则将这个顶点置于链表的头部,对下一个顶点开始Discharge。 Relabel-to-Front算法的时间复杂度是O(V^3),还有一个叫Highest Label Preflow Push的算法复杂度据说是O(V^2*E^0.5)。我研究了一下HLPP,感觉它和Relabel-to-Front本质上没有区别,因为Relabel-to-Front每次前移的都是高度最高的顶点,所以也相当于每次选择最高的标号进行更新。还有一个感觉也会很好实现的算法是使用队列维护溢出顶点,每次对pop出来的顶点discharge,出现了新的溢出顶点时入队。 Push-Relabel类的算法有一个名为gap heuristic的优化,就是当存在一个整数0<k<V,没有任何顶点满足h[v]=k时,对所有h[v]>k的顶点v做更新,若它小于V+1就置为V+1。不过这个我还没实现,因为现在算法的效率我已经很满意了,以后有空再实现吧。 今天实现的Relabel-to-Front比昨天的距离标号最短增广路又要高效一倍左右。最后感叹一下,网络流真是有趣啊……甚至都想买那本专门讲网络流的书来看看。 示例程序(还是USACO Training Ditch,不过都是自己出数据测的): ditch(preflow).cpp