字符串的有关算法讲述ppt课件.ppt

《字符串的有关算法讲述ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、字符串的相关算法还是在前面的话因为本人太弱…所以这几天讲的ppt经常会发现错误，建议在ppt大略的基础上去找相关论文学习。可能重点还是在原理的简单解释…有的地方听不懂的话也没关系，因为每个人没有实现过代码之前实际上都是这样的，可能会对某些地方不理解不影响你对整个算法的印象。以后如果能够专门思考的话也许就会快捷许多。字符串算法有一些的原理看起来比较麻烦，但是代码量往往特别短，所以建议要去完全理解某个算法的原理，这样子以后就算把模板忘了，也许也能够通过原理写出相应的代码。一开始可以学习一下练习模板。字符串算法的模板往往很短，很容易上手。大前天提到了分治

2、…提到了这样一个方程…f(n)=f(n/2)+f(n/2)+O(1)这个咱当时是说f(n)=O(nlogn)那是咱SB…TooNaïve考虑线段树的节点，就是这个分布的…可是线段树的节点个数是O(n)的这个的解显然应该是f(n)=O(n)在此表示歉意咱所知道的字符串算法Pascal的Pos函数…Hash哈希Kmp和扩展KmpTrie树AC自动机后缀树，后缀数组(SA)，后缀自动机(SAM)Manacher算法乱搞最近新出来的：回文自动机(PAM)(太弱不会)。Hash哈希Hash应该都知道…常用的Hash函数?首先直接把每一个字符的ASCII值加起

3、来作为Hash值不取模的情况很容易冲突…常用的Hash，自己设一个X进制(X>=你的字符集的大小-1，比如大写字母有26个字母，字符集大小为26)然后咱们就有Hash=∑S[i]*X^(i-1)假设字符串长度为s，这个就可以在O(s)的时间内算出来。显然如果存的下最后的Hash值的话，每一个字符串的Hash值必定不相同。Q:为什么？实际上这种计算方法，每个字符串都是X进制下的一个数，而Hash值就是这个X进制的数转十进制的值，由于X进制的数互不相同，显然Hash值，即十进制的数也互不相同。Q：那如果字符串长度过大，以致会爆怎么办？取个模呗…Q：那如

4、果两个字符串不同Hash值取某个模最后相同怎么办？取多个模呗…如果多个模的情况下都相同那么就是同一个字符串。Q：如果取多个模都相同呢？……首先，这个模是你自己定的，所以一般数据是没办法全部卡的。接着，由中国剩余定理，只要取到的每个模足够大，那么最后也可以保证一定范围内的Hash值是一定的。Q：中国剩余定理是什么？以后讲数学的时候会讲吧…顺便可以百度_(:зゝ∠)_除了这种Hash以外，字符串Hash也有很多其他的版本，比如ELFhash(黑书上的)据说这个的效果比上面的还好，咱没试过_(:зゝ∠)_FunctionELFhash(vars:stri

5、ng):integer;Varg,h,i:longint;Beginh:=0;fori:=1tolength(s)dobeginh:=hshl4+Ord(S[i]);g:=hand$f0000000($是十六进制)ifg<>0thenh:=hxor(gshr24);h:=hand(notg);end;ELFhash:=hmodM;End;Bzoj1014JSOI2008火星人火星人最近研究了一种操作：求一个字串两个后缀的公共前缀。比方说，有这样一个字符串：madamimadam，我们将这个字符串的各个字符予以标号：序号：1234567891011字

6、符madamimadam现在，火星人定义了一个函数LCQ(x,y)，表示：该字符串中第x个字符开始的字串，与该字符串中第y个字符开始的字串，两个字串的公共前缀的长度。比方说，LCQ(1,7)=5,LCQ(2,10)=1,LCQ(4,7)=0在研究LCQ函数的过程中，火星人发现了这样的一个关联：如果把该字符串的所有后缀排好序，就可以很快地求出LCQ函数的值；同样，如果求出了LCQ函数的值，也可以很快地将该字符串的后缀排好序。尽管火星人聪明地找到了求取LCQ函数的快速算法，但不甘心认输的地球人又给火星人出了个难题：在求取LCQ函数的同时，还可以改变字符

7、串本身。具体地说，可以更改字符串中某一个字符的值，也可以在字符串中的某一个位置插入一个字符。地球人想考验一下，在如此复杂的问题中，火星人是否还能够做到很快地求取LCQ函数的值。字符串长度始终<=10^5，操作数<=10^4题目是什么意思？一般先化成裸题。LCP是最长公共前缀，现给出一个字符串S，支持以下操作：1询问LCP(x,y)，也就是原字符串从x开始的字符串和从y开始的字符串最长的公共前缀2修改，修改原S的一个字符3添加，在S的第X个字符后面添加一个字符。这个有什么做法？也是可以把问题分开来考虑，比如，怎么快速求LCP?Hash?考虑使用Has

8、h来做实际上这里的LCP(x,y)的x,y所代表的字符串都是S的后缀考虑每一个后缀Suffix[i]，就是从S的第i个字符