/ Recent Posts

[算法刷题]滚动哈希Rabin-Karp算法

1147.段氏回文
你会得到一个字符串text 。你应该把它分成k个子字符串(subtext1, subtext2,…, subtextk),要求满足:

  • subtexti非空字符串
  • 所有子字符串的连接等于text(即subtext1 + subtext2 + ... + subtextk == text)
  • 对于所有i的有效值(即1 <= i <= k) ,subtexti == subtextk - i + 1均成立

返回k可能的最大值

Read more →

[算法刷题]后缀数组Suffix Array

后缀数组概念

设有一字符串s

  1. 子串 字符串s的子串为s中从下标i到下标j的连续的一段字符组成的字符串s[i...j],假设字符串下标从1开始.
  2. 后缀 指从某个位置i开始到整个字符串末尾的一个子串,记作suffix(i) = s[i...len(s)].
  3. 字符串大小比较 按字典顺序比较,显然两个不同开头位置的后缀suffix(i)suffix(j)不可能相等,即suffix(i) != suffix(j) (i != j)
  4. 后缀数组 sa为一个一维数组,保存了1~n的某个排列sa[1]、sa[2]、... sa[n],满足suffix(sa[i]) < suffix(sa[i + 1])
  5. 名次数组 rank为一个名次数组,其中rank[i]suffix(i)在所有后缀中从小到大的名次为多少。
Read more →

[C++]advance(), prev() and next()

定义在头文件 <iterator>

std::advance

增加给定的迭代器 it 以 n 个元素的步长。
若 n 为负,则迭代器自减。该情况下, InputIt 必须满足遗留双向迭代器 (LegacyBidirectionalIterator) 的要求,否则行为未定义。

Read more →

All posts →