网站图片分辨率,网络营销方式名词解释,网站建设最低要求,c 做网站后台涉及到字符串的问题#xff0c;无外乎这样一些算法和数据结构#xff1a;自动机 KMP算法 Extend-KMP 后缀树 后缀数组 trie树 trie图及其应用。当然这些都是比较高级的数据结构和算法#xff0c;而这里面最常用和最熟悉的大概是kmp#xff0c;即使如此还是有相当一部分人也… 涉及到字符串的问题无外乎这样一些算法和数据结构自动机 KMP算法 Extend-KMP 后缀树 后缀数组 trie树 trie图及其应用。当然这些都是比较高级的数据结构和算法而这里面最常用和最熟悉的大概是kmp即使如此还是有相当一部分人也不理解kmp更别说其他的了。当然一般的字符串问题中我们只要用简单的暴力算法就可以解决了然后如果暴力效率太低就用个hash。当然hash也是一个面试中经常被用到的方法。这样看来这样的一些算法和数据结构实际上很少会被问到不过如果使用它们一般可以得到很好的线性复杂度的算法。 老实说我也一直觉得字符串问题挺复杂的出来一个如果用暴力hash搞不定就很难再想其他的方法当然有些可以用动态规划。不过为了解决这个老大难问题还是仔细对这些算法和数据结构研读了一番。做个笔记免得忘了还得重新思考老长时间。如果碰到字符串问题也一般不会超过这些方法的范围了。先看一张图吧主要说明下这些算法数据结构之间的关系。图中黄色部分主要写明了这些算法和数据结构的一些关键点。 图中可以看到这样一些关系extend-kmp 是kmp的扩展ac自动机是kmp的多串形式它是一个有限自动机而trie图实际上是一个确定性有限自动机ac自动机trie图后缀树实际上都是一种trie后缀数组和后缀树都是与字符串的后缀集合有关的数据结构trie图中的后缀指针和后缀树中的后缀链接这两个概念及其一致。 下面我们来分别说明这些算法和数据结构并对其涉及的关键问题进行分析和解释。 kmp 首先这个匹配算法主要思想就是要充分利用上一次的匹配结果找到匹配失败时模式串可以向前移动的最大距离。这个最大距离必须要保证不会错过可能的匹配位置因此这个最大距离实际上就是模式串当前匹配位置的next数组值。也就是max{Aj 是 Pi 的后缀 j i}pi表示字符串A[1...i],Aj表示A[1...j]。模式串的next数组计算则是一个自匹配的过程。也是利用已有值next[1...i-1]计算next[i]的过程。我们可以看到如果A[i] A[next[i-1]1] 那么next[i] next[i-1]否则就可以将模式串继续前移了。整个过程是这样的void next_comp(char * str){ int next[N1]; int k 0; next[1] 0; //循环不变性每次循环的开始k next[i-1] for(int i 2 ; i N ; i){ //如果当前位置不匹配或者还推进到字符串开始则继续推进 while(A[k1] ! A[i] k ! 0){ k next[k]; } if(A[k1] A[i]) k; next[i] k; } }复杂度分析从上面的过程可以看出内部循环再不断的执行k next[k]而这个值必然是在缩小也就是是没执行一次k至少减少1另一方面k的初值是0而最多 N次而k始终保持非负很明显减少的不可能大于增加的那些所以整个过程的复杂度是O(N)。 上面是next数组的计算过程而整个kmp的匹配过程与此类似。 extend-kmp 为什么叫做扩展-kmp呢首先我们看它计算的内容它是要求出字符串B的后缀与字符串A的最长公共前缀。extend[i]表示B[i...B_len] 与A的最长公共前缀长度也就是要计算这个数组。 观察这个数组可以知道kmp可以判断A是否是B的一个子串并且找到第一个匹配位置而对于extend[]数组来说则可以利用它直接解决匹配问题只要看extend[]数组元素是否有一个等于len_A即可。显然这个数组保存了更多更丰富的信息即B的每个位置与A的匹配长度。 计算这个数组extend也采用了于kmp类似的过程。首先也是需要计算字符串A与自身后缀的最长公共前缀长度。我们设为next[]数组。当然这里next数组的含义与kmp里的有所过程。但它的计算也是利用了已经计算出来的next[1...i-1]来找到next[i]的大小整体的思路是一样的。 具体是这样的观察下图可以发现 首先在1...i-1,要找到一个k使得它满足knext[k]-1最大也就是说让k加上next[k]长度尽量长。 实际上下面的证明过程中就是利用了每次计算后knext[k]始终只增不减而它很明显有个上界来证明整个计算过程复杂度是线性的。如下图所示假设我们已经找到这样的k然后看怎么计算next[i]的值。设len knext[k]-1(图中我们用Ak代表next[k]),分情况讨论 如果len i 也就是说len的长度还未覆盖到Ai,这样我们只要从头开始比较A[i...n]与A的最长公共前缀即可这种情况下很明显的每比较一次必然就会让inext[i]-1增加一.如果len i,就是我们在图中表达的情形这时我们可以看到i这个位置现在等于i-k1这个位置的元素这样又分两种情况如果 L next[i-k1] len-i1,也就是说L处在第二条虚线的位置这样我们可以看到next[i]的大小至少是len-i1,然后我们再从此处开始比较后面的还能否匹配显然如果多比较一次也会让iA[i]-1多增加1.如果 L len-i1 也就是说L处在第一条虚线位置我们知道A与Ak在这个位置匹配但Ak与Ai-k1在这个位置不匹配显然A与与Ai-k1在这个位置也不会匹配故next[i]的值就是L。 这样next[i]的值就被计算出来了从上面的过程中我们可以看到next[i]要么可以直接由k这个位置计算出来要么需要在逐个比较但是如果需要比较则每次比较会让knext[k]-1的最大值加1.而整个过程中这个值只增不减而且它有一个很明显的上界knext[k]-1 2*len_A,可见比较的次数要被限制到这个数值之内因此总的复杂度将是O(N)的。 trie树 首先trie树实际上就是一些字符串组成的一个字符查找树边由代表组成字符串的字符代表这样我们就可以在O(len(str))时间里判断某个字符串是否属于该集合。trie树的节点内分支可以用链表也可以用数组实现各有优劣。 简单的trie树每条边由一个字符代表但是为了节省空间可以让边代表一段字符这就是trie的压缩表示。通过压缩表示可以使得trie的空间复杂度与单词节点数目成正比。 AC自动机 ac自动机可以看成是kmp在多字符串情况下扩展形式可以用来处理多模式串匹配。只要为这些模式串建立一个trie树然后再为每个节点建立一个失败指针也就是类似与kmp的next函数让我们知道如果匹配失败可以再从哪个位置重新开始匹配。ac实际上两个人的名字的首字母Aho-Corasick。 应该还记得在kmp构造next数组时我们是从前往后构造即先构造1...i-1然后再利用它们计算next[i],这里也是类似。不过这个先后是通过bfs的顺序来体现的。AC自动机的失败指针具有同样的功能也就是说当我们的模式串在Tire上进行匹配时如果与当前节点的关键字不能继续匹配的时候就应该去当前节点的失败指针所指向的节点继续进行匹配。而从根到这个失败指针指向的节点组成的字符串实际上就是跟当前节点的后缀的匹配最长的字符串。 过程如下 --------------引用AC(Aho-Corasick)自动机算法http://hi.baidu.com/luyade1987/blog/item/5ba280828dcb9eb96d811972.html 如同KMP中模式串得自我匹配一样.从根节点开始,对于每个结点:设该结点上得字符为k,沿着其父亲结点得失败指针走,直到到达根节点或者当前失败指针结点也存在字符为k得儿子结点,那么前一种情况当然是把失败指针设为根节点,而后一种情况则设为当前失败指针结点得字符为k得儿子结点. 我们也可以动手操作一下如果我们的ac自动机只包含一个模式串这个过程实际上就是kmp的计算过程。 接下来要做的就是进行文本匹配:首先Trie-(模式串集合)中有一个指针p1指向root,而文本串中有一个指针p2指向串头。下面的操作和KMP很类似如果设k为p2指向的字母 ,而在Trie中p1指向的节点存在字符为k的儿子那么p2,p1 则改为指向那个字符为k的儿子,否则p1顺着当前节点的失败指针向上找直到p1存在一个字符为k的儿子,或者p1指向根结点。如果p1路过一个标记为模式串终点的结点那么以这个点为终点的的模式串就已经匹配过了.或者如果p1所在的点可以顺着失败指针走到一个模式串的终结结点那么以那个结点结尾的模式串也已经匹配过了。在下面的链接中可以找到相关的资料:www.cs.uku.fi/~kilpelai/BSA05/lectures/slides04.pdf 主要是根据模式串构造三个函数goto fail和output. q : 0; // initial state (root)for i : 1 to m dowhile g(q, T[i]) 0 doq : f(q); // follow a failq : g(q, T[i]); // follow a gotoif out(q) ! 0; then print i, out(q);endfor;-----------------------------------------引用结束-------------------------------------------------------------------------------------------以ababa为例我们可以得到它的kmp next数组值为 0 0 1 2 3,ac自动机和trie图如下 trie图 trie图实际上一个确定性自动机比ac增加了确定性这个属性对于ac自动机来说当碰到一个不匹配的节点后可能要进行好几次回溯才能进行下一次匹配。但是对于trie图来说可以每一步进行一次匹配每碰到一个输入字符都有一个确定的状态节点。 从上面的图中我们也可以看到trie图的后缀节点跟ac自动机的后缀指针基本一致区别在于trie图的根添加了了所有字符集的边。另外trie图还会为每个节点补上所有字符集中的字符的边而这个补边的过程实际上也是一个求节点的后缀节点的过程不过这些节点都是虚的我们不把它们加到图中而是找到它们的等价节点即它们的后缀节点从而让这些边指向后缀节点就可以了。(比如上图中的黑节点c它实际上并未出现在我们的初始tire里但我们可以把它作为一个虚节点处理把指向它的边指向它的后缀节点) trie图主要利用两个概念实现这种目的。一个是后缀节点也就是每个节点的路径字符串去掉第一个字符后的字符串对应的节点。计算这个节点的方法是通过它父亲节点的后缀节点很明显它父亲的后缀节点与它的后缀节点的区别就是还少一个尾字符设为c。所以节点的父节点的指针的c孩子就是该节点的后缀节点。但是因为有时候它父亲不一定有c孩子所以还得找一个与父亲的c孩子等价的节点。于是就碰到一个寻找等价节点的问题。 而trie图还有一个补边的操作不存在的那个字符对应的边指向的节点实际上可以看成一个虚节点我们要找一个现有的并且与它等价的节点将这个边指向它。这样也实际上是要寻找等价节点。 我们看怎么找到一个节点的等价节点我们所谓的等价是指它们的危险性一致。那我们再看一个节点是危险节点的充要条件是它的路径字符串本身就是一个危险单词或者它的路径字符串的后缀对应的节点是一个危险节点。因此我们可以看到如果这个节点对应的路径字符串本身不是一个危险单词那它就与它的后缀节点是等价的。所以我们补边的时候实际指向的是节点的后缀节点就可以了。 trie图实际上对trie树进行了改进添加了额外的信息。使得可以利用它方便的解决多模式串的匹配问题。跟kmp的思想一样trie图也是希望利用现在已经匹配的信息对未来的匹配提出指导。提出了一些新的概念。定义trie树上从根到某个节点的路径上所有边上的字符连起来形成的字符串称为这个节点的路径字符串。如果某个节点的路径字符串以一个危险字符串结尾那么这个节点就是危险节点也就是说如果到达这个点代表是匹配的状态否则就是安全节点。 那么如何判断某个节点是否危险呢 根节点显然是安全节点。一个节点是危险节点的充要条件是它的路径字符串本身就是一个危险单词或者它的路径字符串的后缀(这里特指一个字符串去掉第一个字符后剩余的部分)对应的节点(一个字符串对应的节点是指从trie图中的根节点开始依次沿某个字符指定的边到达的节点)是一个危险节点。 那么如何求每一个节点的后缀节点呢这里就可以里利用以前的计算信息得到了。具体来说就是利用父亲节点的后缀节点我们只要记住当前节点的最后一个字符设为C那么父亲节点的后缀节点的C分支节点就是要求的后缀节点了。首先我们限定根节点的后缀节点是根本身第一层节点的后缀节点是根节点。这样我们可以逐层求出所有节点的后缀节点。但是这个过程中可能出现一个问题父亲节点的后缀节点可能没有c分支。这时候该怎么办呢 如下图所示如果设当前节点的父亲节点的后缀节点为w我们假设w具有c孩子为我们可以看到对于w的整个c子树来说因为根本不存在通向它们的边c它们也就不可能是不良字符串这样这些节点的危险性也就等价与它们的后缀节点的危险性了而它们的后缀节点实际上就是w的后缀节点的c孩子如此回溯下去最后就能找到。 --------------------引用http://huangwei.host7.meyu.net/?paged7 其实Trie图所起到的作用就是建立一个确定性有限自动机DFA图中的每点都是一个状态状态之间的转换用有向边来表示。Trie图是在Tire的基础上补边过来的其实他应该算是AC自动机的衍生AC自动机只保存其后缀节点在使用时再利用后缀节点进行跳转并一直迭代到找到相应的状态转移为止这个应该算是KMP的思想。这篇文章可以参考。 而Trie图直接将AC自动机在状态转移计算后的值保存在当前节点使得不必再对后缀节点进行迭代。所以Trie图的每个节点都会有|∑|个状态转移∑指字符集。构造具体方法可见WC2006《Trie图的构建、活用与改进》。我简单叙述下流程1构建Trie并保证根节点一定有|∑|个儿子。2层次遍历Trie计算后缀节点节点标记没有|∑|个儿子的对其进行补边。后缀节点的计算1根结点的后缀节点是它本身。2处于Trie树第二层的节点的后缀结点也是根结点。3其余节点的后缀节点是其父节点的后缀节点中有相应状态转移的节点这里类似AC自动机的迭代过程。节点标记1本身就有标记。2其后缀节点有标记。补边用其后缀节点相应的状态转移来填补当前节点的空白。最后Trie图中任意一个节点均有相应的状态转移我们就用这个状态转移做动态规划。设dp[i][j]表示第i个状态产生j个字符时与DNA序列最小的改变值。假设Tire图中根节点是0则初始化dp[0][0]1。其后对图进行BFS遍历可知处于第j层时就说明以产生了j长度的字符串。dp[0][0] 1;for i 1 to m do for 图中每条边(s1,ch,s2) do dp[s2][i] min{dp[s1][i-1] (txt[i-1] ! ch)}; for 图中每个结点x do ans min{dp[x][m]}; -----------------------------------------------引用结束----------------------------------------------------------------------------------- 后缀树 后缀树实际上就是字符串的所有后缀组成的字符串集合构成的trie树。如果采用不压缩方式的trie存储这样整个内部节点和外部节点的总和就可能达到O(n^2).所以不能利用这种存储方式因为如果采用它那么构建的复杂度下界就是O(n^2)不会再低了。所以必须使用压缩方式才有可能降到O(n)。 构建之前我们首先给字符串加上一个未在字符串中出现过的单词比如$,为什么这样做呢是为了避免后缀节点出现在内部如果我们加上$很明显就不会有后缀出现在内部了可以用反证法证明假设出现了一个这样的后缀是内部节点那么意味着这条字符串路径上会有两个$,但这是不可能的因为我们的$只在结尾出现之前没有出现过。 构建过程中我们看如果采用普通的构建过程是怎样的普通的构建假设字符串为A[1....N],我们从以A[1]开头的后缀开始插入trie树插入的时候逐步比对直到找到不匹配的分支在这个节点将原来的节点分裂并加入这个新的节点。可以这个过程关键是寻找之前sufix[1]...sufix[i-1]这些已经插入的字符串与sufix[i]的最长公共前缀。之后插入的时间O(1)就可以完成因此主要的时间花在这个最长公共前缀(称为head[i])的寻找上。Headi是W(i,n)和W(j,n)的最长公共前缀其中j是小于i的任意正整数Taili使得Headi Taili W(i,n)。 那我们看到现在关键是这个最长公共前缀head[i]的计算了。我们再次考虑如何利用head[1]...head[i-1]来计算head[i],为加快寻找hi的速度我们需要使用辅助结构——后缀链接。 后缀链接的定义McCreight Arithmetic令Head[i-1] az其中a是字符串W的第i-1位字符。由于z在范围i内出现过至少两次(因为az也是A[i-1...N]与之前某后缀的最长公共前缀也就是说另外的那个后缀也是一az开头的一个串这样就意味着它的后继者就比然是以z为前缀的这样A[i...N]与它的公共前缀就是z。{实际上这个性质在我们计算后缀数组的lcp时也会利用到})所以一定有|Head[i]| |z|z是Head[i]的前缀。所谓hi-1的后缀链接Suffix Link实际是由hi-1指向z对应节点d的指针Link h[i-1]。当然z有可能是空串此时Link hi-1由hi-1指向根节点Root。 和前面 ac自动机的失败指针 trie树的后缀指针比较我们可以发现这里的z它刚好就是head[i-1]去掉第一个字符后的那个后缀所谓的后缀链接实际上是指向head[i]自身的后缀的链接这个定义也就跟我们trie树里的后缀指针所指向的那个位置一致了。这样这个head[i]的后缀链接怎样建立就很清楚了。 创建方法1根节点Root的后缀链接指向它自身2任何一个非叶节点的后缀链接都在该节点出现以后被立即创建 算法主框架如下For i 1 - n do 步骤1、函数Find从Link hi-1开始向下搜索找到节点hi 步骤2、增添叶子节点Leafi 步骤3、函数Down创建hi的后缀链接Link hi End for 后缀树性能分析接着刚才文本框内的伪代码来谈论。对于给定的i步骤2的复杂度为O(1)但由于无法确定Link hi-1到hi之间的节点个数所以不能保证步骤1总是线性的。局部估算失败不妨从整体入手。有一点是肯定的那就是i |Headi|总随着i的递增而递增。因此W中的每个字符只会被Find函数遍历1次总体复杂度是O(n)的。 这个分析就与extend-kmp的复杂度分析很类似了。 后缀数组 后缀数组实际上就是对字符串的后缀按照字典序进行排序然后把排好序后的顺序放到一个数组sa[]里保存数组元素代表了后缀在原串里的起始索引。通过这个我们可以很容易得到另一个数组rank[],rank[i]代表了原来的后缀A[i...N]在sa数组里的排名。 这个数据结构主要涉及两个方面的内容一个是如何快速的对这些后缀排序有很多方法这里只说明倍增算法这个方法比较好理解思路也比较巧妙。 还有就是后缀数组求出来后如果要发挥比较强的作用还需要求出各个后缀的最长公共前缀lcs。所以lcs的计算也是一个重点。 首先看排序如果我们采用普通的排序算法那么需要nlogn次比较但是每次比较需要O(n),这样总的复杂度将是O(n*nlogn). 倍增算法是这样的,主要是第i次排序比较时的大小时利用了第i-1次的排序结果这样可以让比较在O(1)时间里完成我们首先对所有从原字符串各个位置开始的长度为1的字符进行排序然后再对从这些位置开始的长度为2的排序之后是长度为2^i的排序直到2^i N.可以看到这中间总共需要log N次排序。然后我们看第i次排序比较大小时怎样利用了第i-1次的排序结果。 比如在第i次排序时我们需要比较A[j]和A[k]开始的长度为2^i的串那么我们可以将它们分成两块A[j]开始的长度为2^i的串 A[j]开始的2^(i-1)长 A[j2^(i-1)]开始的2^(i-1)长A[k]开始的长度为2^i的串 A[k]开始的2^(i-1)长 A[k2^(i-1)]开始的2^(i-1)长要比较A[j]开始的长度为2^i的串 和 A[k]开始的长度为2^i的串我们只要先比较第一部分如相等再比较第2部分而这两部分大小因为之前已经排好序了我们完全可以给它们一个rank值只比较它们的rank值就可以得到大小关系这样比较就可以在O(1)时间内完成了。另外如果我们的排序算法是O(n)的这样整个算法的复杂度就是O(nlogn)的了。 再看lcs的计算如果要计算任意两个后缀的lcs[i][j]我们有一个结论 设 ij LCP(i,j)min{LCP(k-1,k)|i1 k j} LCP Theorem 这里的ij指而是sa[i] sa[j] 如果要证明上面那个结论首先要证明这个对任意的 1ijkn, LCP(i,k)min{LCP(i,j),LCP(j,k)}这里不再证明。 上面那个结论实际上说如果要找i j的最长公共前缀长度只需要找到i j之间相邻后缀的最小lcs长度即可。这样我们只需要求出sa数组中相邻后缀的lcs长度就转化成了一个rmq问题即区间内的最小值问题。这个可以O(1)解决。这样问题就变成如何在O(n)时间里计算sa数组中相邻后缀的lcs长度。 这个问题如果要O(n)又利用了下面这样一个结论定义一个一维数组 height令height[i]LCP(i-1,i) 1in 并设 height[1]0。如何尽量高效的算出height数组呢 为了描述方便设h[i]height[Rank[i]]即height[i]h[SA[i]]而h数组满足一个性质 对于 i1 且 Rank[i]1 一定有 h[i] h[i-1]-1. 为什么会有这个结论呢实际上就与上面后缀树的后缀链接那部分提到的想呼应了。h[i]height[Rank[i]],实际上就是我们的原来的后缀A[i...N]与某个串的最长公共前缀而h[i-1]就是A[i-1...N]与某个串的最长公共前缀。而我们可以看到如果把A[i-1...N]去掉第一个字符后就变成了A[i...N]我们假设A[i-1...N]相邻的那个后缀串是XYYYYYY在这里它们的lcs长度是h[i]。后缀串XYYYYYY去掉x之后就是YYYYYYY,这样如果没有比它更接近A[i...N]的,那么h[i]h[i-1]-1,如果A[i...N]的邻居不是它那么h[i]只可能比h[i-1]-1大不可能比它小。 这样利用这个结论我们在O(n)时间内就可以把h[i]计算出来了。因为h[i]最大不超过N而它每次最多减少不超过1. 计算出来之后再根据height[i]h[SA[i]]就可以计算出height数组这样就求出了sa中相邻后缀的lcs长度。 总结实际上我们可以看到上面的算法思想都有一个共同点利用已经得到的计算结果得到下一次计算的结果尽量利用现有信息减少计算量。转载请注明作者phylipsbmy 出处http://duanple.blog.163.com/blog/static/709717672009825004092/ 转载于:https://www.cnblogs.com/10jschen/archive/2012/09/24/2700761.html
