1   来到网易实习

这些天我一直在后悔一件事情，就是还没看保密协议上面都写有些什么就把它给签了………而且到目前为止我还不知道上面写了些什么。

嗯，透露一下下肯定不是商业机密的事情吧，网易的伙食还不错。

2   晒晒我的 vimrc

分到电脑的那一天花了一个上午装各种软件，其中最耗精力的要数 VIM 了，自己的 vimrc 没有随身带着，又考虑到里面塞满了各种从网上看到的看上去很好玩但实际上一万年用不到一次的设置，所以干脆自己重新写了一份，里面全是每天都会用到的东西，不长：

set nocompatible
source $VIMRUNTIME/mswin.vim
behave mswin

if has("gui_running")
  colo Ifs
  set gfn=consolas:h11
  set go-=m
  set go-=T
  set cursorline
else
  colo blue
  set nocursorline
endif

syntax on
filetype on
filetype indent on
filetype plugin on

map  <space> :
map  <C-j> <C-w><down>
map  <C-k> <C-w><up>
map  <C-h> <C-w><left>
map  <C-l> <C-w><right>
imap <C-j> <down>
imap <C-k> <up>
imap <C-h> <left>
imap <C-l> <right>

let mapleader=";"
map <leader>w :w!<cr>
map <leader>q :close<cr>
map <leader>[ <C-o>
map <leader>] <C-]>
map <leader><space> <C-w>

map <leader>j :bn<cr>
map <leader>k :bp<cr>
map <leader>bd :bd<cr>

map <leader>tn :tabnew<cr>
map <leader>l  :tabn<cr>
map <leader>h  :tabp<cr>
map <C-t>      :tabnew<cr>
map <C-tab>    :tabn<cr>
map <C-S-tab>  :tabp<cr>

map <silent> <leader><cr> :noh<cr>

map <leader>tl :TlistToggle<cr>
map <leader>gf :NERDTree<cr>

set history=50
set autoread
set ts=4
set expandtab
set smarttab
set shiftwidth=4
set autoindent
set smartindent
set cindent
set scrolloff=5
set wildchar=<Tab>
set wildmenu
set cmdheight=1
set ruler
set nu
set lz
set hid
set whichwrap+=<,>,h,l
set ignorecase
set incsearch
set magic
set showmatch
set hlsearch
set laststatus=2
set statusline=\ %P\ %F%m%r%h\ %y\ %w\ \ CWD:\ %{getcwd()}%h\ \ Line:\ %l/%L:%c
set showmatch
set showmode

其中 <space> 和 <leader> 的设置照目前看来貌似很非主流，但是 <space> 不映射成 : 实在是可惜了，毕竟向下滚动有 j 就够了，而且 j 很好用，把 <space> 映射成 : 可以在敲命令的时候感觉十分痛快；另外 ; 就在小拇指上面，用来敲快捷键再方便不过，默认的用于重复 f, t, F, T 的操作也是基本上用不到的，所以，嗯……

这个设置没考虑到 Linux 下的情况，不过除了 gfn 之外其他应该没什么需要改动的吧。另外 Ifs 主题是我在 lettuce 主题的基础上改的，自己喜欢而已。

插件装得不多，因为发现插件多了启动会慢：

• bufexplorer
• c
• mark
• matchit
• NERD_tree
• supertab
• taglist

c.vim 要修改一下，它有个 <leader>lcs 的映射，除了让我的 <leader>l 响应变慢之外啥用途都没有，罪过很大。

——然后用起来就很舒服了。

3   Qt，各种吐槽

最新版本的 Qt 光是安装文件竟然就有 1.5 GB !!! 它完全疯了!!!

有段时间特别喜欢 Qt，因为它的每个类都显得非常漂亮，比如说字符串类里面会提供宽字符和窄字符的转换，再比如说 QImage 类光是构造函数就有这么多种：

• QImage ()
• QImage ( const QSize & size, Format format )
• QImage ( int width, int height, Format format )
• QImage ( uchar * data, int width, int height, Format format )
• QImage ( const uchar * data, int width, int height, Format format )
• QImage ( uchar * data, int width, int height, int bytesPerLine, Format format )
• QImage ( const uchar * data, int width, int height, int bytesPerLine, Format format )
• QImage ( const char * const[] xpm )
• QImage ( const QString & fileName, const char * format = 0 )
• QImage ( const char * fileName, const char * format = 0 )
• QImage ( const QImage & image )

不但功能上一应俱全，而且甚至不需要任何文档，一眼看上去就能知道每个函数是怎么用的。

让人不爽的还是 C++ 的二进制不兼容问题，上次做的一个小实验清楚的说明了想让不同的 C++ 编译器生成的二进制程序共用一个 C++ 类实在是很难的事情；而更早之前的经验表明即使是同一个编译器，不同的版本之间也不见得可以兼容，坑爹啊，也就是说你根本提供不了一个统一的运行时环境，写了个好玩的程序想发给别人装 B，只有每次都把一堆几十 MB 的 dll 和自己几 kb 的程序放在一起才行...这不是比 .Net 还过分吗...

还有，很大程度上托无所不能的 template 的福，C++ 编译的那速度... 上次编译 Qt 4.6 花了 4 个小时左右，后来我专门统计了一下，不算文件头注释和空行，Qt 4.6 一共有 2362083 行代码[1]，按 4 个小时来算的话，那么编译+链接速度平均就是每秒钟 164 行了，还有什么语言能比它更慢一点的！！

怎么好像在对 C++ 吐槽……

……都怪 Qt 太大了， FLTK 这种 kb 级别和谁都能静态链接在一起的图形库，用 C++ 我当然没意见，否则您丫每隔一两月更新一次，每次都扔给我好几 G 的东西，还让我以前的程序面临死翘翘的危险，太过分了。

4   乱七八糟

今天在 cnBeta 上看到一句话 “别人一开源，我们就自主研发了。” 笑死了

“搞ACM的你伤不起[2]” - 一看就知道是大牛手笔

1. C++ 很变态

去网易面试了，一个 C++ 上的问题把我难到了：“多重继承的时候子类是不是要保存每个父类的虚函数表？”

我回答 “通常是的，但虚继承的时候好像 %#@$%#^&*” —— 其实我就记得虚继承的时候情况很有点乱，忘了究竟有多乱。

回来之后做了个实验：

#include <iostream>
#include <iomanip>
#ifdef _MSC_VER // 老兄，特立独行的永远是你！！
typedef unsigned int uint32_t;
#else
#include <stdint.h>
#endif

using namespace std;

class A
{
public:
    uint32_t x;
    uint32_t y;
    A():x(42),y(24){}
    virtual void f(){
        cout<<"A::f()    [this="<<this
            <<"]; this->x="<<x<<"; this->y="<<y<<";\n";
    }
};

class B:virtual public A
{
public:
    B():A(){}
};

class C:virtual public A
{
public:
    C():A(){x=21,y=12;}
    virtual void f(){
        cout<<"C::f()    [this="<<this
            <<"]; this->x="<<x<<"; this->y="<<y<<";\n";
    }
};

class D:public B, public C
{ 
public:
    D():A(),B(),C(){}
};

template<class T>
void showDetail(T const& v)
{
    int s=sizeof(T)/4;
    uint32_t const* p=reinterpret_cast<uint32_t const*>(&v);
    cout<<"  +-------------+\n";
    for(int i=0;i<s;++i) {
        cout<<"  | "<<setw(11)<<p[i]<<" | ";
        if(p[i]>10000) { // suppose it's a pointer
            cout<<" -> "<<*reinterpret_cast<uint32_t const*>(p[i]);
        }
        cout<<endl;
    }
    cout<<"  +-------------+\n";
}

int main(){
    A a;
    B b;
    C c;
    D d;
    cout<<"a:\n";
    showDetail(a);
    cout<<"b:\n";
    showDetail(b);
    cout<<"c:\n";
    showDetail(c);
    cout<<"d:\n";
    showDetail(d);
    return 0;
}

为的是看看虚继承的时候到底发生了什么，结果又是大出意外，GCC, M$VC, DigitalMars 编译出来的竟各不相同：

GCC

a:  +-------------+
    |     4666904 | -> 4324460
    |          42 |
    |          24 |
    +-------------+

b:  +-------------+
    |     4666924 | -> 0
    |     4666936 | -> 4324460
    |          42 |
    |          24 |
    +-------------+

c:  +-------------+
    |     4666956 | -> 4324764
    |     4666972 | -> 4631892
    |          21 |
    |          12 |
    +-------------+

d:  +-------------+
    |     4666988 | -> 4
    |     4667000 | -> 4324764
    |     4667016 | -> 4631892
    |          21 |
    |          12 |
    +-------------+

M$VC

a:  +-------------+
    |     4305572 | -> 4198672
    |          42 |
    |          24 |
    +-------------+

b:  +-------------+
    |     4305668 | -> 0
    |     4305664 | -> 4198672
    |          42 |
    |          24 |
    +-------------+

c:  +-------------+
    |     4305632 | -> 0
    |           0 |
    |     4305628 | -> 4217088
    |          21 |
    |          12 |
    +-------------+

d:  +-------------+
    |     4305684 | -> 0
    |     4305632 | -> 0
    |           0 |
    |     4305680 | -> 4217088
    |          21 |
    |          12 |
    +-------------+

DigitalMars

a:  +-------------+
    |     4448636 | -> 4205756
    |          42 |
    |          24 |
    +-------------+

b:  +-------------+
    |     4448640 | -> 0
    |     4581960 | -> 5856153
    |     4448636 | -> 4205756
    |          42 |
    |          24 |
    +-------------+

c:  +-------------+
    |     4448660 | -> 4205896
    |     4448648 | -> 0
    |     4448656 | -> 4203244
    |          21 |
    |          12 |
    +-------------+

d:  +-------------+
    |     4448660 | -> 4205896
    |     4448672 | -> 0
    |     4448664 | -> 0
    |     5838868 | -> 4500440
    |     4448680 | -> 4203252
    |          21 |
    |          12 |
    +-------------+

好吧，看这情景，我怎么回答都算不上错，因为哪有正确答案啊。

可惜把 Borland C++ Builder 和 Open Watcom 编译器都删了，不然如果看到 5 种不同的结果岂不是更欢乐～ 唉，难怪 C++ 木有 ABI。

另外，被问到虚函数表在对象的什么部位时我发烧似的答道“在尾部”，囧啊，谁教我的。（不过另一方面，可以诡辩一下的是， C++ 2003 标准甚至没有规定运行期多态一定要以虚函数表的形式实现，只是目前的编译器不约而同的采用了虚函数表而已，所以，嗯...）

Update:

Open Watcom 编译出来的结果是这样的：

a:
  +-------------+
  |          42 |
  |          24 |
  |     4240484 | -> 4198782
  +-------------+
b:
  +-------------+
  |     4240544 | -> 0
  |           8 |
  |          42 |
  |          24 |
  |     4240556 | -> 4198782
  +-------------+
c:
  +-------------+
  |     4240488 | -> 0
  |     4240500 | -> 4198952
  |          12 |
  |          21 |
  |          12 |
  |     4240508 | -> 4198866
  +-------------+
d:
  +-------------+
  |     4240520 | -> 0
  |     4240532 | -> 4198952
  |     4240512 | -> 8
  |          16 |
  |          21 |
  |          12 |
  |     4240540 | -> 4199045
  +-------------+

果然又不同——不过，惊喜啊，它还真把虚函数表放在了尾部。

2. 脑袋短路

还是网易面试，几个算法题都发挥得不够满意，甚至包括生成随机数的题，回头想想也有改进的空间。

嗯...不知道试题有没有涉及到某种需要保密的东西，所以暂时先不谈好了……

3. 春天来了

1   Prologue

本篇文章主要针对的是对字符串匹配有兴趣的生物以及被某版本数据结构与算法教材中的 KMP 算法讲解弄得不知所云但与此同时却还难能可贵地保持着旺盛求知欲的不幸生在了错误年代的可怜童鞋，其他生物阅读本文前请慎重考虑因为它 可能对您的大脑（如果有）、小脑甚至包括脊髓都造成严重且不可恢复的创伤 。

2   Notations

下文可能会提到 “模式串”、“文本串”、“窗口” 这些词，它们的定义如下，如果这些文字使你头晕，请及时做好救治准备。

模式串、文本串

所谓 模式串 ，是指你想要找到（或者得到位置 &etc.）的字符串；而 文本串 ，则是指搜索的目标字符串。

比如说你要在 "lucky dog" 中寻找 "dog" ，那么 "dog" 是模式串， "lucky dog" 则是文本串；

而你若要在 "If is a lucky dog" 中寻找 "lucky dog" ，那么 "lucky dog" 便成了模式串， "If is a lucky dog" 则是文本串。

Understand?

窗口

无论用什么样的搜索算法，在搜索的过程中，总是需要将模式串与文本串进行比较，它们对齐的那部分区域，也就是们关心的那块区域，咱称为 窗口 。

另外，为了避免让已经适应 C/C++/C#/D/Java/JavaScript/Python/Go/... 语言思维的童鞋多绕一个弯，本文用到的数组下标都以 0 开始 —— 甚至包括费波拉契数列也如此。

3   Main Idea

MP/KMP 字符串搜索算法的思想精华在于利用已经匹配的部分包含的信息，加速搜索的过程。

嗯——已经匹配的部分包含什么信息？

它已经匹配了！

举例说，在某个字符串中查找子串 A B C D A B D A C 时，如果遇到 A B C D A B ，而紧跟其后的不是 D ，这时候我们可以将窗口右移四位（而不是一位），因为既然 A B C D A B 已经匹配了， 那么移动当前窗口之后 已经匹配过的地方 肯定需要保证 依然匹配 ，这里最好的做法即让 A B 相互对齐:

. . A B C D A B ? . . . . . .
    A B C D A B D A C

=>

. . A B C D A B ? . . . . . .
            A B C D A B D A C

因为，看呀，如果只右移一位，那么:

. . . . . . . . . . . . . . . // 先不用管这个字符串
    A B C D A B . . .         // 已经匹配的部分
=>    A B C D A B D A C
      |
    糟糕！

如上面所示， A B C D A B 匹配了，那么移动一位之后，第一个字符 A 就肯定会对着 B ，绝对不可能在这个地方找到匹配

右移两位、三位或者四位时发生的状况可以依此类推；而右移四位时就不同了:

. . . . . . . . . . . . . . . // 暂时还不用管这个字符串
    A B C D A B . . .         // 已经匹配的部分
=>          A B C D A B D A C

这个时候才 可能 成功匹配。

4   MP 算法

0: /*Empty*/
1: A
2: A B
3: A B C
4: A B C D
5: A B C D A

0: /*Empty*/
1: B
2: A B
3: D A B
4: C D A B
5: B C D A B

int MP(char const* pattern, char const* text)
{
    int i=0,j=0,m=strlen(pattern);
    int F[m];
    calcF (pattern, F); // 计算跳转数组
    for(;text[i];++i,++j) {
        while(j>=0 && pattern[j]!=text[i]) {
            // 第一个字符不匹配则右移窗口、从 0 开始比较
            if (j==0) {
                j=-1;
                break;
            }
            j = F[j-1]; // 对齐
        }
        if(j>=m-1) {    // 找到了！
            return (i+1-m);
        }
    }
    return -1;
}

1.  A B C D A B D A C
    A B C D A B D A C
    |
    0  // 定义为 0

2.    A B C D A B D A C
    A B C D A B D A C
      |
      0 // 匹配部分的长度

3.      A B C D A B D A C
    A B C D A B D A C
        |
        0

4.        A B C D A B D A C
    A B C D A B D A C
          |
          0

5.6.        A B C D A B D A C
    A B C D A B D A C
            | |
            1 2

7.              A B C D A B D A C
    A B C D A B D A C
                |
                0

8.                A B C D A B D A C
    A B C D A B D A C
                  |
                  1

9.                  A B C D A B D A C
    A B C D A B D A C
                    |
                    0

void calcF(char const* pattern, int* F)
{
    int i=0,j=0;
    for(;pattern[i];++i,++j) {
        while(j>0 && pattern[j-1]!=pattern[i]) {
            j = F[j-1];
        }
        F[i] = j;
    }
}

int MP(char const* pattern, char const* text)
{
    int i=0,j=0,m=strlen(pattern);
    int F[m+1];
    calcF (pattern, F); // 计算跳转数组
    for(;text[i];++i,++j) {
        while(j>=0 && pattern[j]!=text[i]) {
            j = F[j];   // 对齐
        }
        if(j>=m-1) {    // 找到了！
            return (i+1-m);
        }
    }
    return -1;
}

void calcF(char const* pattern, int* F)
{
    int i=0,j=-1;
    F[0]=-1;
    for(;pattern[i];++i,++j) {
        while(j>=0 && pattern[j]!=pattern[i]) {
            j = F[j];
        }
        F[i+1] = j+1;
    }
}

5   KMP 算法

其实 MP 算法的效率还有提升的空间，不过从模式串 A B C D A B D A C 中看不明显；我们试试这样一个模式串： A B A B A B C 。

假设在 A B C A B C A B A B A B C A C 中查找 A B A B A B C ，按照 MP 算法的思想，先算出 F 数组：

于是查找的过程就是这样的：

1.  A B C A B C A B A B A B C A C
    A B A . . . .

2.  A B C A B C A B A B A B C A C
        A . . . . . .

3.  A B C A B C A B A B A B C A C
          A B A . . . .

4.  A B C A B C A B A B A B C A C
              A . . . . . .

5.  A B C A B C A B A B A B C A C
                A B A B A B C

从第 1 步到第 2 步、从第 3 步到第 4 步，我们发现，字符 A 与 C 的不匹配导致了第一次失败，然后紧接着又直接导致了第二次失败。

如此，我们又惊喜的发现，在 A B 之后若是遇到不是 A 的字符，我们完全可以跳三步！因为跳两步的话算是把 A 对齐了 —— 可是它们会被对齐到一个不是 A 的、将会导致匹配失败的字符上面去。

这样的规则有什么规律呢？我直接放出代码吧：

// 这是我们计算 MP 算法中的 F 数组的函数：
void calcF(char const* pattern, int* F)
{
    int i=0,j=-1;
    F[0]=-1;
    for(;pattern[i];++i,++j) {
        while(j>=0 && pattern[j]!=pattern[i]) {
            j = F[j];
        }
        F[i+1] = j+1;
    }
}

睁大眼睛准备找茬喽：

// 只需要改一句话：
void calcF(char const* pattern, int* F)
{
    int i=0,j=-1;
    F[0]=-1;
    for(;pattern[i];++i,++j) {
        while(j>=0 && pattern[j]!=pattern[i]) {
            j = F[j];
        }
        // !这里!
        F[i+1] = pattern[j+1] == pattern[i+1]?
                   F[j+1]:
                   j+1;
    }
}

为什么呢？因为对于同一个字符导致的失败，失败在前面应该跳到哪里，到后面就还是应该跳到哪里。

另外，这个时候咱似乎就比较喜欢把这个数组称作 next 数组了 —— 其实还是同一回事。

那么， A B A B A B C 的 next 数组如下，请您欣赏：

6   复杂度分析

至于为什么 KMP 算法的复杂度是线性的，我们再回头看看 另一种表示 一节中的算法主体：

int MP(char const* pattern, char const* text)
{
    int i=0,j=0,m=strlen(pattern);
    int F[m+1];
    calcF (pattern, F);
    for(;text[i];++i,++j) { // j 增大，i 增大
        while(j>=0 && pattern[j]!=text[i]) {
            j = F[j];       // j 减小
        }
        if(j>=m-1) {
            return (i+1-m);
        }
    }
    return -1;
}

i 只有增大的份，所以 ++i 最多执行 n 次，这个很显然。

j 初始值为 0，一共增加了 n 次，而 j>=-1 ，于是 j = F[j] 这一句最多也就执行了 n+1 次（否则就会出现 j<-1 的情况了）。

所以就是线性的了！

7   KMP 算法的最长停顿

为了说明 KMP 算法在文本串上的某一个字符上进行了很多次比较的极限情况（也就是所谓的停顿或者E文的 delay ），我们首先要介绍一下 “费波拉契串” —— 因为，很巧，它就是能使 KMP 算法达到最糟糕状况的模式串，一会儿我们会说到。

提到 “费波拉契” ，相信不少人会直接想到 1, 1, 2, 3, 5, 8, 13, 21, 34 ... ，是的，费波拉契串的定义也十分类似：

设 P 是个费波拉契串，那么：

P[0] = b
P[1] = a
P[i] = P[i-1]P[i-2]

所以：

P[2] = ab
P[3] = aba
P[4] = abaab
P[5] = abaababa
P[6] = abaababaabaab
P[7] = abaababaabaababaababa
P[8] = abaababaabaababaababaabaababaabaab
...

计算出 P[7] 的 F 数组和 Next 数组如下，我们一会儿要用到，你也可以先把它当作找规律的题看看：

费波拉契串有几个性质值得注意一下：

1. strlen(P[n]) == Fibonacci[n] （这个应该很容易理解吧）

2. 设函数 c(t) 的作用是交换字符串 t 的最后两个字符，例如 c("abcdef") == "abcdfe"，那么当 n>=2 时 P[n-1]P[n-2] == c(P[n-2]P[n-1]) ：

   n == 2 时这是显然的；

   当 n>2 时可以用数学归纳法证明：

   c(P[n-2]P[n-1]) = P[n-2]c(P[n-1]) = P[n-2]P[n-3]P[n-2] = P[n-1]P[n-2]
3. 由上面两条性质我们又可以推导出：

   Next[Fibonacci[n]-2] == F[Fibonacci[n]-2] == Fibonacci[n-1]-2, n>=2

   这是因为，可以把一个费波拉契串分解开：

   P[n] == P[n-1]P[n-2] == P[n-2]P[n-3]P[n-2] == c(P[n-3]P[n-2])P[n-2] == P[n-3]c(P[n-2])P[n-2] == ...

   具体以 P[7] 为例，

   P[7] == ab-ab-ba---ab------ba

   其中省略掉的部分根据 性质2 表现出的规律与前方相等，因此如果在 P[7] 的最后一个字符 b 处发生了不匹配，接下来应该在下列位置重新试着匹配：

   ab-a--b----a-------b-

   它们正好占据着 Fibonacci[2]-2, Fibonacci[3]-2, .. , Fibonacci[7]-2, ... 的位置。

因此，如果在费波拉契串的第 n 位，n == Fibonacci[k]-2 上发生了不匹配，接下来则还需要 k-1 次比较；

又因为 Fibonacci[k-1] == (φ^k - (-1)^kφ^-k)/sqrt(5) == round( φ^k / sqrt(5) )， 于是可以解得 k ~ log_φ(n)，其中 φ 是黄金比例 (1+sqrt(5))/2 == 1.618...

—— k 便是文本串上的一个字符的最多比较次数。

8   为什么费波拉契串这么神奇

为了证明为何费波拉契串就是使停顿时间最长的模式串，我们再看看 MP 算法的基本思想：将字符串已匹配的一个前缀和一个对应的后缀匹配。

假设字符串 S 有且仅有一个相等的前缀和后缀（设为 a ），那么 S 可以表示为

S = aB = Ca

再假设 a 本身也有且仅有一个相等的前缀和后缀（设为 e ），那么 a 也可以表示为

a = eF = Ge

对应 MP 算法，匹配 Ca 时若在 a 之后失败，则会将 aB 的 a 与其对齐：

Cax
Cay

==>

Cax
 aBy

若在 B 的第一个字符处再次失败，则下一次对齐是这样的：

CGex
 GeBy

==>

CGex
  eFBy

KMP 算法在这里还要求 F 的第一个字符和 B 的第一个字符不等（否则会跳过这一段）

我们很容易可以证明想要 KMP 算法在这个地方停留尽可能长的时间需要满足 |S| <= |e| + |a| ：因为若 |e| + |a| > |S|，那么令 d = |e| + |a| - |S| 则 Ca = CGe = aB 算式中， a 和 e 将有长度为 d 的重叠，于是 B 的第一个字符等于 e[d]；同理，在 aB = eFB = Ca 算式中，可以得到 F 的第一个字符为 a[d]，由 a = eF 可以得到 a[d] = e[d]，和 KMP 的要求不符。

于是 |S| == |e| + |a| 是使 KMP 算法的停顿时间达到最长的极限情况——很容易发现，满足这条件的便是费波拉契串了。

9   PS

对了，如果我要找出模式串在文本串中所有的出现怎么办？

提示一下：目前为止 F 数组（或者 next 数组）的最后一个元素我们还没有用到过是不是？

10   References

Last update: 2010/11/23 18:53:11