最大公约数和最小公倍数

  public static long gcb(long a, long b) {
        return b == 0 ? a : gcb(b, a % b);
   }
// 最小公倍数
 public static long lcm(long a, long b) {
        return a / gcb(a, b) * b;
 }

Manacher

• Manacher算法，又叫“马拉车”算法，可以在时间**O(N)**的情况下求解一个字符串的最长回文子串长度的问题。
• 求解一个字符串的最长回文子串长度的问题另外一个写法,时间复杂度 O($n^2$)
  • 在每个字符串之间加入一个标志位，例如 11311 -> #1#1#3#1#1#
  • 然后每个索引上的值向左右遍历对比。
  • 拿到最大的长度， 长度/2 就是最长回文子串的长度

概念

• 回文直径，回文半径
• 一个数组：每个索引上能建立的最大的回文半径
• 最大回文右边界 例如 012131210 最大回文边界为第二个0
• 最大回文有边界的中心

思路

• 在每个字符串之间加入一个标志位，例如 11311 -> #1#1#3#1#1#

2. i位置不再回文右边界里面，继续暴力求出在i+1的回文子串长度
3. i位置在回文右边界内，根据回文中心c，做出i的对称点$i_2$
   1. $i_2$的回文直径在当前c的回文半径中，例如 z k [ a b($i_2$) a t f(c) t a b(i) a ] k u
   • 此时i的回文半径和$i_2$一致
   2. $i_2$的回文半径的索引超出了当前c的回文半径，例如a b [c d($i_2$) c b a t t(c) t a b c d(i) c] f
      • 此时i的回文半径为i到c的右边界的长度
   3. $i_2$的回文半径的索引等于了当前c的回文半径，例如 t [a b c($i_2$) b a k(o) a b c(i) b a] k
      • 此时i的回文半径无法确认，要从c的右边界的下一个继续校验

KMP字符串模式匹配算法

• 主要解决包含的问题。例如：str1的子串集合中是否包含str2
• 时间复杂度 O(n)
• 思路
  • next数组： str2中不含当前字符，当前字符之前的字符串,前后缀的最大相等的长度(不能包含整体) 由此可得 0位置永远是-1，1位置永远是0, 举例： i前面的字符是 aabaab则最大前后缀相等的长度是3
  • 如何加速的
    • 当找到不匹配的字符x时，看对应的str的X1的最大前后缀相等的长度是len，当前位置x直接和str2中的 len 位置进行匹配(因为0占了一个位置，所以不用+1)
  • 如何加速构建next数组
    • 求i位置的next 值，看 i-1位置的最大长度len，然后比较len 和 i-1 的值是否相等 相等则是len+1 否则看i-1位置的最大长度的next[len]的最大长度是len1 然后比较 len 位置和 i-1 位置是否相等 相等则是len1 +1 ，一直重复知道跳到 尽头nuxt[len] = 0 则len 是0

BFPRT算法(TOP-K)

应用

• 用来求元素中第k大（或小）的值或是前k大（或小）的值 时间复杂度O(N)

思路

• 快排的优化,优化了partition过程，在partition中根据所要找的数，只对左侧或者右侧进行递归partition
• 过程
  1. 5个分一个组
  2. 将各个组排序
  3. 拿到每个数组的中位数组成一个新数组midArr
  4. 用midArr作为参数递归调用bfprt算法得到midArr的中位数
  5. 将该中位数作为partition的划分值来做partition,直到找到第K个大(小)的数

窗口最大最小值的更新结构(单调双向队列)

• 需要一个双端队列存储值和下标，队列的值从大到小排列
• 窗口中加数的逻辑
  • 加的数从队尾插入双端队列，并且要保证是从大到小的顺序，如果不符合先弹出双端队列中的值在塞入当前数及其索引
  • 例如： 窗口中的数为 5 4 1 2 5 6 则此时双端队列中只有6
• 窗口中减数的逻辑
  • 查看当前双端队列的头节点所存储的索引是否为当前要弹出的数的索引，如果是，则从双端队列弹出头节点

跳表

• 跳表实际上是一种增加了前向指针的链表，是一种随机化的数据结构，实质上是可以进行二分查找的有序链表；跳表在原来的有序链表上加上了多级索引，通过索引来快速查找；可以支持快速的删除、插入和查找操作。

• 

TrieTree

• 字典前缀树

布隆过滤器

• 比特数组的容量m计算公式
  • $m= -\frac{NlnP}{ (ln2 )^ 2}$ bit
  • N为样本量，P:预期失误率 不是百分数
• 比特数组中的插值数量(哈希函数的个数)k
  • k = $ln2 * \frac{m}{n}$
• 失误率P
  • $P = (1 - e^{-\frac{n*k}{m}})$