Suffix Automaton

后缀自动机是一个有向无环图,节点为状态,有向边为状态转移边的一种有限状态自动机,它可以且仅可以接受一个字符串的所有后缀,并且状态数和转移数都是最少的。

定义

后缀自动机(suffix automaton,以下简称 SAM)的结构包含两部分,有向无环单词图(directed acyclic word graph,以下简称 DAWG)和前缀树(prefix tree)。 SAM 中的每个节点都同时存在于这两个结构中。

我们对一个字符串 \( S \) 构造其 SAM,称 \( S \) 是该 SAM 的 母串(String) ;下文中提到的「子串(Substring)」、「前缀(Prefix)」与「后缀(Suffix)」,如非特殊说明,均指母串的「子串」、「前缀」与「后缀」。

记 \( | S | \) 为字符串 \( S \) 的长度。

DAWG

顾名思义,DAWG 是一个 DAG(有向无环图)。

DAWG 中,除 起始节点(Start) 外,每个 节点(Node) 表示一个或多个子串。

节点之间通过 转移边(Transfer arc) 相连,每条转移边上有一个 字符(Char)

从起始节点沿着转移边走,每条 路径(Path) 都对应着一个子串,即将走过的边上的字符首尾相连得到的子串(显然多条路径会到达同一个节点上)。

我们称在 SAM 上运行一个字符串 \( S \) ,即为从 DAWG 的起始节点开始,第 \( i \) 次沿着字符 \( S_i \)​​ 的转移边走,走完 \( |S| \) 次;如果 \( S \) 是母串的一个后缀,则称到达的节点为 可接受 的节点。

由于 SAM 是一个自动状态机,所以节点也被称为 状态(State)

为什么pass的密码仓库能上传到github?

pass 内置了上传与获取git仓库数据的指令,且官方在教程中也推荐把 .password-store 提交到github,这不禁让人疑惑:"这样真的安全吗?"

确实, .password-store 位于用户 HOME 目录下,是用户使用 pass 时存储所有密码的文件夹,暴露出去在直观上的确感觉很不安全,令人担忧。

但是, .password-store 中所有密码都是通过 gpg 加密的,只要 .password-store 中的数据不足以破解密文,那么用户的所有密码数据都是安全的!

.password-store 中的数据并没有直接记录任何加密用的密钥信息,pass 和 gpg 的配合方式保证了这一点。

后缀数组-倍增法-详解

Prologue

倍增法 求字符串的 后缀数组 本质上其实并不难,但是基于 多个数组与基排序 的实现却非常令人迷惑 —— 众多的数组以及更多的循环让初学者一片混乱,包括我。

本文会由浅入深逐步讲解后缀数组、倍增法以及逐步的优化,并在最后附上完整的代码与基准测试结果。

代码均由 golang 实现,但是不用担心,不会有语法问题困扰你。

什么是后缀数组?

后缀数组( Suffix Array )是一个有序数组,其元数为某一个字符串的所有后缀。

比如:

给定字符串 banana 。显然它所有的后缀为: {"banana", "anana", "nana", "ana", "na", "a"} 。不过,这种表示方式冗长且浪费空间,我们可以直接将其简化为 {0, 1, 2, 3, 4, 5} ,其中每个元素都代表该后缀首字母在原本字符串中的索引号。我们设该数组为 Origin

若要根据 Origin 求出 banana 的后缀数组,我们只需要对 Origin 排序即可:

Origin                            SuffixArray

0 banana 5 a
1 anana Sort the Suffixes 3 ana
2 nana ----------------> 1 anana
3 ana alphabetically 0 banana
4 na 4 na
5 a 2 nana

所以, banana 的后缀数组为 {5, 3, 1, 0, 4, 2} 。(在本文中为升序)

正如我们所见的,后缀数组本身并不复杂,或则说定义很简单,其高深晦涩的地方在于 通过何种高效的排序方式得出后缀数组

买或不买?这种题目最无聊了!

题目: 1004. To Buy or Not to Buy - Hard Version (35)

此非贪心,亦非动态

当我第一次读完题目时,我天真的以为这道题不是 动态规划 就是 贪心

然而在我无数次思考其最优子结构后,发现这个最优子结构存不存在都没有关系!直接看下面这个状态转移公式:

A[0][j] = INFINITY
A[m][j] = min{A[m-1][j], A[m-1][j ^ (j&k)] + extra beads in m}

Tarjan算法求无向图的割点与桥

该算法是R.Tarjan发明的。过程与求强连通图的类似。wiki

求割点

基本概念

割点:无向图连通分量中,如果删除其中某点以及与该点相连的边后,连通分量变成不连通,则称该点为割点。

实现

在Tarjan算法的过程中,当前结点u是割点的条件为:

  1. u 为在 dfs 上的根结点, 即 u 的 father 为 nil , 此时需要满足 u 的子结点数量要大于 1 且其中至少有一个子结点满足 v.index==v.lowlink
  2. u 为非根结点, u.index == u.lowlink

注意:度为1(不考虑重边的情况下)的结点虽然满足以上条件,但是不是割点。

Dual Boot - linux pc机上安装win10

一般来说,制作双系统pc时,在linux pc上安装windows是一种不明智的行为。但是,有些时候迫于无奈,我们也会遇到这种情况,~~真是糟糕~~。本文记载我遇到的两种不同启动系统时的解决方式。

BIOS Systems

  1. 为win10腾出空间
  2. 安装win10
  3. 挂载/boot目录或分区
  4. 安装引导程序(GRUB)

Install Opencv with python3 on MacOS

首先 tap homebrew/science

brew tap homebrew/science

The tap command allows Homebrew to tap into another repository of formulae. Once you've done this you've expanded your options of installable software.

These additional Git repos (inside usr/local/Library/Taps) describe sets of package formulae that are available for installation.

homebrew/science 中有两个版本的 opencv,分别是 opencvopencv3 。一个是 stable 2.4.13.2 版本的,另一个是 stable 3.2.0 版本的,你可以通过 brew info 命令查看它们的具体信息。

Django websocket

Django Websocket

Django isn't supported websockt by default!

在十几年前,网站并不复杂,绝大部分网页都是静态页面。以数据库为后端、mvc架构的web应用是夺人眼球的事物,但是现在,依靠ajax获得全部相关数据的单页面web应用也已经随处可见。当然,随处可见的还有依靠websocket实现的实时的web应用。

Django 作为有十几年年龄的web框架,它的内核是基于简单的请求-响应概念建成的:浏览器发出一个请求,Django 接收到后调用一个相应的 view 函数,该函数会返回一段响应数据,然后 Django 将这段数据发送回浏览器。

nil

这不适用于WebSockets!view 仅存在于单个请求的生命周期,并没有机制去处理 打开一个连接发送数据给没有相关联的特定的一个客户端

解决 Django model 的 field 的 default 没生成到sql语句中的问题

本文适用于 python3Django (1.10.5)

在一个app的model中,为 Field 设定 default 关键字参数后,由Django生成的创建相应table的sql语句中,并没有如愿地包含default描述。

比如,

在app的model.py文件中包含:

class Test(models.Model):
price = models.IntegerField(default=0)

运行 ./manage.py makemigrations && ./manage.py sqlmigrate ... 后,Django 生成下列 SQL:

CREATE TABLE `test` (
`id` integer AUTO_INCREMENT NOT NULL PRIMARY KEY,
`price` integer NOT NULL
);

解决方案,改动django源码:

[翻译] Go Walkthrough: io package

原文

Go 是一种被设计为处理bytes数据的编程语言。无论你拥有的是bytes数组,bytes数据流,或者是单个byte,Go 使它易于处理。自那些简洁的原语,我们构建我们的抽象概念和服务。

io 包是标准库中最基础的包之一。它为处理bytes数据流提供了一个接口和辅助函数的集合。

Reading bytes

当处理bytes时,有两个基础的操作:reading 和 writing。让我们先看一下读取bytes。

Reader interface

为从数据流中读取bytes的基础结构是 Reader 接口:

type Reader interface {
Read(p []byte) (n int, err error)
}

这个接口的实现遍及标准库,从 network connectionsfiles, 再到 wrappers for in-memory slices