字符串匹配摘要.pptx

字符串匹配;给定一个长度不超过n的长字符串A和若干个长度不超过m的短字符串B1…Bm 对于每个短字符串，找出它在长字符串中出现的所有位置。 例：ababcababcabc ababc 则返回0,5;枚举全部n个起始位置，依次进行字符串匹配。 时间复杂度：O(nm) 每次字符串匹配没有利用前一次的结果 如何利用字符串B的一个已匹配前缀来减少比较次数？;;假设当前匹配以第i位为起始位置，0~k位匹配成功，k+1位匹配失败。 则以第i+j位为起始位置，0~k-j位可以匹配成功的条件是字符串B的0~k-j位和j~k位相同。 若j=1时不满足，则可以跳过以接下来1位为起始位置的匹配，以此类推。;定义next[]数组，对于字符串B长度为i的前缀，next[i]取值为：小于i，且令其长度为next[i]的前缀和后缀为相同字符串的最大值。 例：ababc i 1 2 3 4 5 next[i] 0 0 1 2 0 若从第i位开始，前3位(aba)匹配成功，第4位匹配失败，则无需从第i+1位开始，因为前2位的ba必然无法匹配ab，而从第i+2位开始，前1位的a可以匹配a。;使用：当前匹配位数为k而出现匹配失败时，将当前匹配位数直接改为next[k]，继续在A的相同位置匹配，若仍匹配失败就继续改为next[next[k]]… 生成： 若B串第i位和第next[i]位相同，则next[i+1]=next[i]+1 否则考虑第i位和第next[next[i]]位… 若均不同，next[i+1]=0;1.生成next[]数组。时间复杂度O(m) 2.利用next[]数组进行匹配。时间复杂度O(n);求给定字符串（长度S=400000）所有满足前缀和后缀相同的长度。 求给定字符串（长度S=10^6）最多是由其一个子串重复多少次得到的。 求给定字符串（长度S=10^6）的所有由其一个子串重复=2次得到的前缀，输出前缀长度和重复次数。;;定义：一个确定有穷自动机（DFA）M是一个五元组：M=（K，Σ，f，S，Z）其中 ① K是一个有穷集，它的每个元素称为一个状态； ② Σ是一个有穷字母表，它的每个元素称为一个输入符号，所以也称Σ为输入符号字母表； ③ f是转换函数，是K×Σ→K上的映射(且可以是部分函数)，即，如 f（ki，a）=kj，（ki∈K，kj∈K）就意味着，当前状态为ki，输入符为a时，将转换为下一个状态kj，我们把kj称作ki的一个后继状态； ④ S ∈ K是唯一的一个初态； ⑤ Z?K是一个终态集，终态也称可接受状态或结束状态。 ;DFA以如下方式接受或拒绝一个字符串：从初始状态出发，对于输入字符串中的每个字符，自动机都将沿着一条确定的边到另一状态，这条边必须是标有输入符号的边。对n个字符的字符串进行了n次状态变换后，如果自动机到达了一个终态，自动机将接收该字符串。若到达的不是终态，或者找不到与输入字符相匹配的边，那么字符串将拒绝接受这个字符串。 由一个自动机识别的语言是该自动机接收的字符串集合。 ;;如果省略KMP算法中沿next[]数组寻找一个有效前缀的过程，就构成了一个自动机。 例：ababc（省略的边全部指向起点） 生成方法： 1、按照字符串生成边，按照next[]数组生成next[]指针。 2、若某状态对于某字符没有转移，则沿着它的next[]指针寻找是否有转移。 实际运用中往往只生成next[] 指针而不生成完整的自动机。;对于状态x，考虑它在字符串中的上一个状态f，若是通过字符ch到达的x，且next[f]对于字符ch有转移到y，则next[x]=y。若不然，再考虑next[next[f]]，以此类推。 f = x-fat; while (x != root f-child[ch] == NULL) f = f-next; x-next = f-child[ch]; ;AC自动机是KMP算法在具有多个模式串时的优化。 在匹配失败时，KMP只会考虑当前字符串的前缀，而AC自动机能将多个短字符串的前缀一并考虑，在实际运行时较为迅速。;DNA序列由A,T,C,G四种碱基的排列组成。给出m=10个疾病的DNA序列，且长度均=10，问长度为n=2*10^9的所有可能的DNA序列中不含上述所有序列的排列种类数，模100000输出。 m=50，长度=20，并给出一个长度=1000的原串，问至少修改其中几个字符能使得原串不含上述所有序列。若无论如何修改都不能则输出-1。;;比较两个字符串是否相等需要O(len)的时间。而比较两个int类型的数据是否相等只需要O(1)的时间。 如果构建一个函数f:string-int，在需要比较字符串A和B时通过比较f(A)和f(B)代替，就可以极大降低时间复杂度。此函数即为hash函数。 通常可