MP/KMP 算法详解

By If

Contents

• 1   Prologue
• 2   Notations
• 3   Main Idea
• 4   MP 算法
  
  • 4.1   原理
  • 4.2   跳转数组的计算
  • 4.3   另一种表示
  • 4.4   可是...
• 5   KMP 算法
• 6   复杂度分析
• 7   KMP 算法的最长停顿
• 8   为什么费波拉契串这么神奇
• 9   PS
• 10   References

自解压不神奇

小时候总以为自解压文件肯定用到了某种诡异的 PE 格式上的 trick，要不然 Linux 下为什么没怎么见过自解压的东东呢。

然而昨天翻 7-zip 代码的时候惊讶的发现了真相——
你应该已经注意到了，7-zip 可以打开自解压文件。


——所以？

Mosaic

以前看Matrix67大牛介绍过用Mathematica制作马赛克拼贴图像的东东，然后自己也试了一下下。
我的故事是，今天灵光一闪，我想到其实每个小图片包含的信息是很多的，只取一个平均值真是太委屈它了，用“高级一点的”图像近似度计算方法肯定可以得到不错的效果，于是我自己瞎掰了一个匹配算法：取缩略图；高斯模糊；比较方差——发现效果果真（相对）还行：

一个烂尾工程：JavaScript 的 BrainFK 解释器

前几天看到Matrix67大牛推荐的名曰Manufactoria的编程游戏，非常之喜欢，玩得快要通关的时候，转念一想，诶，玩这个还不如玩BF呢。

嗯，要么我自己写个类似的BF的网页游戏？

这么一冲动，就刷刷刷写了下面的东西——剩下来的工作主要就是界面了，结果我又发现我没有时间做那工作，还得复习啊。
所以……这个烂尾工程就这么捐出来算了罢，下面的代码属于公有领域

WildCard 通配符的粗糙实现

话说今年学校又举行 ACM 程序设计竞赛了，这次我有机会出题目吓一吓那些小孩子们，心里很得瑟呢。
本意是想要出一道模拟题判断一个五子棋棋局的胜负状况；但是很神奇的是，一念之间，我就产生了一个新的想法，考 '*' 和 '?' 通配符吧。
WildCard 说起来是匹配，实际上更像是查找：比如说用 ab*??ab*ab 匹配 abababababab ，不是从头到尾比对一遍就能完成的事情，所以让他们做这道题肯定会很有乐趣。

life.cpp

#include "exceptions.hpp"
#include "human.hpp"
#include "school.hpp"
#include "food.hpp"
#include "life.hpp"

void life::eat(food &f) {
    if(!f.tasty())
        throw(error("WTF is it?!"));
    else {
        this->money -= f.price();
        f = excrement;
        this->grow();
    }
}

void life::sleep() {
    int sheep;
    for(sheep = 0; !asleep(); ++sheep)
        if(sheep<0)
            throw(astonishment("OMG!"));
    this->grow();
}

void life::work( thing& t ) {
    t = nothing;
    error up("Okay, I messed it up");
    throw up;
}

void life::haveFun() {
    throw(error("How is it possible?"));
}

void life::live() {
    while(this->alife_) {
        eat();
        work();
        haveFun();
        eat();
        sleep();
        work();
        haveFun();
        eat();
        work();
        haveFun();
        sleep();
    }
}