## 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++

## 算法设计与分析笔记0x10 —— Extending the Limits of Tractability

Must sacrifice one of three desired features.

• Solve problem to optimality.
• Solve problem in polynomial time.
• Solve arbitrary instances of the problem.

## 算法设计与分析笔记0x0F —— PSPACE

P Decision problems solvable in polynomial time.
PSPACE Decision problems solvable in polynomial space.

• P PSPACE
• 3-SAT is in PSPACE
• NP PSPACE

## 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?

## 算法设计与分析笔记0x0C —— Part 1 NP完全

Algorithm design patterns.

• Greedy.
• Divide-and-conquer.
• Dynamic programming.
• Max-flow min-cut.
• Reductions.

Algorithm design anti-patterns.

• NP-completeness.
• PSPACE-completeness.
• Undecidability.

## 数据排序

• .sort_index()方法在指定轴上根据索引进行排序，默认升序
• .sort_index(axis=0, ascending=True)
• For DataFrame, first argument is some index or columns by which data is sorted.
• NaN统一放在排序末尾

## Pandas库介绍

• Python第三方库，基于Numpy，提供高性能易用数据类型和分析工具
• import pandas as pd