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

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

CIRCUIT-SAT. Given a combinational circuit built out of AND, OR, and NOT gates, is there a way to set the circuit inputs so that the output is 1?
Theorem CIRCUIT-SAT is NP-complete.

### 算法设计与分析笔记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.

### 微博数据爬取

• 爬取内地、港台明星势力榜前50名的明星近期微博数据。
• http://chart.weibo.com/?rank_type=3&version=v1
• http://chart.weibo.com/?rank_type=5&version=v1

• 爬取共100名明星微博。
• 共计24219条微博。

### Sketchy OAuth2 & Docker & SSH

I wrote this post for Environment Setup & Basic Knowledge for Data Science. (of course under Ubuntu16.04, but also other Debian systems should be OK)

For python, I’ve written a series of notes. https://today2tmr.com/2017/07/18/python-爬虫学习笔记目录/ https://today2tmr.com/2017/12/13/python-数据分析与展示笔记目录/

## OAuth2

Authorization Grant Types
Refer to http://www.ruanyifeng.com/blog/2014/05/oauth_2_0.html

• 授权码模式 Authorization Code
• User-Agent applies for code
• Client uses code to apply for token
• 简化模式 Implicit
• Client applies for token directly
• 密码模式 Resource Owner Password Credentials
• User tells Client password to apply for authorization.
• 客户端模式 Client Credentials
• Client applies for authorization in the name of itself.

### English Linking Patterns and Rules

B站王霸胆视频的学习笔记 https://www.bilibili.com/video/av5243511/

Take place between LAST syllable of the first word and FIRST vowel of the second word.

## Pattern 1: Unvoiced -> Voiced

• t/s/f -> d/z/v
• trends to be voiced consonant