使用Burkhard-Keller tree优化近似串匹配

Approximate string matching

近似字符串匹配问题。

Levenshtein edit distance

在metric space中衡量两个字符串差异程度的一个指标,即通过一系列单字符的编辑操作把字符串A变成字符串B所需的最小编辑次数,其中的编辑操作可以是插入字符、删除字符以及修改字符。

计算编辑距离有个经典的Wagner-Fischer算法,使用了动态规划,用d(i,j)表示把字符串A的前i个字符变成字符串B的前j个字符所需的最小编辑次数(即子串的编辑距离)。

Read More

RuCTFE 2012参赛记

海底捞火锅

RuCTFE 是一个面向全世界的信息安全比赛,每个队伍保护自己的机器,攻击其他队伍的机器,长达8个小时紧张激烈的对抗和赛前犒赏队员的火锅标志着它是这一年我参与的最有意义的事之一,因而在这里简要记录下来。有幸收到《Metasploit渗透测试指南》的译者孙松柏的邀请,成为 blue-lotus 队的一员,和网络安全实验室的同学一起出发,晚上一群人去吃牡丹园的海底捞火锅壮行。

Read More

基于 mutt+offlineimap+notmuch+inotifywait 的个人邮件系统

收邮件

早先使用getmail + procmail。缺点是本地对邮件的操作无法在服务器上反映出来。

使用offlineimap可以利用Gmail的filter功能,把邮件分拣到本地的各个maildir子目录。

注意在Gmail上设置filter规则时,要选上Skip Inbox,以免一封邮件同时出现在分类子目录和INBOX中。请看下面这条示例规则:

Read More

完美迷宫生成算法

Perfect maze

Perfect maze又称standard maze,指没有回路,没有不可达区域的迷宫。用图论的语言来说,就是可以用spanning tree表示的迷宫,保证迷宫中任意两个格子间都有唯一的路径。本文旨在探讨如何随机生成棋盘状perfect maze。迷宫格子的邻居的定义采用von Neumann neighborhood,即水平竖直方向相邻的四个格子。

变形Kruskal算法

说得通俗点,就是“随机拆墙”。

Read More