算法导论笔记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完全”

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.

Continue reading “Sketchy OAuth2 & Docker & SSH”