算法导论笔记0x16 —— 子串搜索

KMP

m is the length of text
n is the length of pattern

  • [Prefix Array Logic]
  • 初始j指向0索引,i指向1索引
  • 数组0索引初始化为0
  • 检查匹配
    • 不匹配时,跳到j索引的前一个数组值所对应的索引位置继续检查匹配
      • 不匹配时,j=Array[j-1]
      • 若j是0,数组值为0,Array[i]=0
    • 匹配时,数组中的值为j的值加1,i和j同时加1继续检查匹配
      • Array[i]=j+1, i++, j++

Continue reading “算法导论笔记0x16 —— 子串搜索”

算法设计与分析笔记0x0E —— Part 3 NP完全

Partitioning Problems

3-Dimensional Matching

3D-MATCHING. Given n instructors, n courses, and n times, and a list of the possible courses and times each instructor is willing to teach, is it possible to make an assignment so that all courses are taught at different times?
3D-MATCHING. Given disjoint sets X, Y, and Z, each of size n and a set T X × Y × Z of triples, does there exist a set of n triples in T such that each element of X Y Z is in exactly one of these triples?

Continue reading “算法设计与分析笔记0x0E —— Part 3 NP完全”

算法设计与分析笔记0x09 —— 网络流

Max-flow and Ford-Fulkerson Algorithm

  • 网络流是一个有向图,源点s,汇点t
  • 每条边流量f(e)不能超过容量c(e)
  • 守恒: 指向结点的流量之和($\sum_{e\,in\,to\, v}f(e)=\sum_{e\,out\,of\,v}f(e)$)等于流出结点的流量之和 (except source and sink points)
  • 流的值: 流出源点的流量综合 $v(f)=\sum_{e\,out\,of\,s}f(e)$.
  • Max flow problem 找到 s-t flow 使其流的值最大
  • Greedy algorithm: 局部最优, 非全局最优.
    • Start with f(e) = 0 for all edge e ∈ E.
    • Find an s-t path P where each edge has f(e) < c(e).
    • Augment flow along path P.
    • Repeat until you get stuck.

Continue reading “算法设计与分析笔记0x09 —— 网络流”