有哪些信誉好的足球投注网站- 1、本文档共7页，可阅读全部内容。
- 2、有哪些信誉好的足球投注网站（book118）网站文档一经付费（服务费），不意味着购买了该文档的版权，仅供个人/单位学习、研究之用，不得用于商业用途，未经授权，严禁复制、发行、汇编、翻译或者网络传播等，侵权必究。
- 3、本站所有内容均由合作方或网友上传，本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺！文档内容仅供研究参考，付费前请自行鉴别。如您付费，意味着您自己接受本站规则且自行承担风险，本站不退款、不进行额外附加服务；查看《如何避免下载的几个坑》。如果您已付费下载过本站文档，您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等，请点击“版权申诉”（推荐），也可以打举报电话：400-050-0827(电话支持时间：9:00-18:30)。
查看更多
知识精炼（一）
主讲人：邓哲也
POJ2774LongLongMessage
给出两个字符串S和T，求它们的最长公共子串。
|S|,|T|≤105
POJ2774LongLongMessage
2
原始的DP做法，时间复杂度O(n)
我们可以二分答案len。
然后计算S和T中所有长度为len的子串的哈希值。
这一步是O(n)的。
然后比较S的哈希值集合中和T的哈希值集合中有没有相
同的元素。
可以再通过一步哈希找相同的值。这样总共仍然是O(n)。
总的时间复杂度就是O(nlogn).
Codeforces580EKefaandWatch
给出一个数字串，现在有两种操作：
1lrd:将[l,r]中的所有数字都改为d
2lrd：询问[l,r]这个子串的周期是否为d。
1=n=105
Codeforces580EKefaandWatch
首先思考对于一个字符串S，如何判断它的周期是不是d？
比如串ababab的周期是2
串abcabc的周期是3
串abcde的周期是5
假设S的长度为n。
只要判断S[1..n-d+1]和S[d+1..n]是否相等即可。
Codeforces580EKefaandWatch
用线段树来维护哈希值。
对于一个区间[l,r]维护的是s[l]kr-l+s[l+1]kr-l-1
+…+s[r]
那么合并两个区间的时候：
h[x]=h[ls]kr-mid+h[rs]即可。
对于覆盖标记（节点为x，代表区间为[l,r]）：
r-lr-l-10
h[x]=d*(k+k+…+k)
这样每次的操作都是O(logn)的。
下节课再见
文档评论（0）