2016年12月

线段树模板

线段树模板,支持对区间做运算并求sum,基于POJ 3468
需要注意:

  • 数组开4倍大
  • 因为区间操作较频繁故打标记
  • 注意Update操作的位置
  • 均为1~n,所以包括左右,分段递归注意端点要被包含

- 阅读剩余部分 -

配置instantclick支持prism高亮与mathjax

由于instantclick实现的是PJAX,headfooter之间的内容并不会更新,而这一部分我加载了渲染代码高亮的prism.jsMathjax以及谷歌的analytics.js,所以貌似除了Google其他的js都不会正常加载,根据instantclick官网的说明,只需要改动一下绑定的事件即可,加载instantclick的部分修改为如下

- 阅读剩余部分 -

后缀数组

最长公共子串问题(LCS)

  • 定义:给定字符串长度最大的公有子串,使用后缀数组可达到$O(nLlogL)$,其中$n为字符串个数$,$L$为每个字符串长度
  • 等效于求两个后缀的公共前缀(LCP)

后缀数组相关概念

  • SA[i]:排名为i的后缀的位置(第i是谁)
  • Rank[i]:第i个后缀suffix(i)的排名
  • 对于已经排好序的字符串,任意两个的公共最长前缀为$LCP(s[i], s[j]) = min \{ LCP(s[k], s[k + 1]) , i \le k < j\}$,LCP转化成区间最小值RMQ问题
  • height[i]:定义height[i] = LCP(SA[i - 1], SA[i]),则$LCP(s[i], s[j]) = min \{ height[k] , i \le k < j\}$

- 阅读剩余部分 -

最新文章

最近回复

分类

归档

其它

微博

基佬们

Fork me on GitHub