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. 春天来了

此段已经加入到了俺写的 MP/KMP 算法详解 中了；缺少这一段正是它一直保持着草稿状态的主要原因；但由于害怕疏忽，目前也还不敢改变其状态。(囧)

好吧，下面开始正文

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 算法的停顿时间达到最长的极限情况——很容易发现，满足这条件的便是费波拉契串了。

1. 我干了什么

我写了个小程序，用 1.276 秒找出了《银河系漫游指南》和《宇宙尽头的餐馆》的最长公共子串：

the history of every major galactic civilization tends to pass through three distinct and recognizable phases, those of survival, inquiry and sophistication, otherwise known as the how, why and where phases.

用 1.266 秒找出了《宇宙尽头的餐馆》和《再见，谢谢所有的鱼》的最长公共子串：

in the uncharted backwaters of the unfashionable end of the western spiral arm of the galaxy

用 8.671 秒找出了《魔戒》和《1984》的最长公共子串：

. it was inevitable that they should make

用 6.728 秒找出了《飘》和《基本无害》的最长公共子串：

more than anything else in the world.

...

我发现这是件很好玩的事情～

2. 怎么做的

Again，有了 后缀树 ，这样的工作太简单了：

/*
 * Author  : If
 * Date    : Oct/16th/2010
 * License : Boost License v1

Permission is hereby granted, free of charge, to any person or organization
obtaining a copy of the software and accompanying documentation covered by
this license  (the "Software")  to use,  reproduce,  display,  distribute,
execute, and transmit the Software, and to prepare derivative works of the
Software, and to permit third-parties to whom the Software is furnished to
do so, all subject to the following:

The copyright notices in the Software and this entire statement, including
the above license grant, this restriction and the following disclaimer,
must be included in all copies of the Software, in whole or in part, and
all derivative works of the Software, unless such copies or derivative
works are solely in the form of machine-executable object code generated by
a source language processor.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED,  INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE, TITLE AND NON-INFRINGEMENT. IN NO EVENT
SHALL THE COPYRIGHT HOLDERS OR ANYONE DISTRIBUTING THE SOFTWARE BE LIABLE
FOR ANY DAMAGES OR OTHER LIABILITY, WHETHER IN CONTRACT, TORT OR OTHERWISE,
ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
DEALINGS IN THE SOFTWARE.
*/

#include "suffixtree.h"
#include <algorithm>
#include <iterator>
#include <iostream>
#include <fstream>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <ctime>
using namespace std;

static void ticToc_(bool s)
{
    static clock_t start_ = clock();
    if(s) {
        start_ = clock();
    } else {
        clock_t end_=clock();
        std::cerr
            << (end_ - start_) << " ticks"
            << "    (" << (end_ - start_) * (1000.)/CLOCKS_PER_SEC <<"ms)"
            << std::endl;
    }
}

inline void tic()
{
    ticToc_(true);
}

inline void toc()
{
    ticToc_(false);
}

struct Info
{
    vector<int> belongTo;
};

typedef Node<char, Info>       NodeT;
typedef SuffixTree<char, Info> STree;

// 初始化节点的从属属性。
void initInfo(NodeT& leaf)
{
    NodeT* node = leaf.parent;
    int    nth  = leaf.belongTo;
    while ( node->parent!=node && (
            node->info.belongTo.empty() ||
            node->info.belongTo.back()!=nth )) {
        node->info.belongTo.push_back(nth);
        node=node->parent;
    }
}

void printPath(NodeT const* node)
{
    if(node->parent!=node)
        printPath(node->parent);
    copy(node->str, node->str+node->len,
         ostream_iterator<char>(cout));
}

// 将连续的空白字符转换成单个空格；将大写全转换为小写。
void filter(char * text, int & len)
{
    char*p=text,*q=text;
    for(;q<text+len;++p,++q){
        if(*q>='A'&&*q<='Z') {
            *p=*q-'A'+'a';
        } else if(isspace(*q)) {
            *p=' ';
            while(isspace(*q))
                ++q;
            --q;
        } else {
            *p=*q;
        }
    }
    len = p-text;
}

struct LetsRock
{
    NodeT const*& result;
    int   longestNow;
    int   nStrings;
    LetsRock(int n, NodeT const*& root):
        result(root),
        longestNow(0),
        nStrings(n)
    { }
    void operator()(NodeT const& node) {
        if (node.depth + node.len > longestNow &&
            node.info.belongTo.size()==nStrings) {
            longestNow = node.depth + node.len;
            result     = &node;
        }
    }
};

int main(int c,char**v)
{
    STree tree;
    tic();
    for(int i=1;i<c;++i) {
        cerr<<"reading "<<v[i]<<" ...\n";
        FILE*  file = fopen(v[i],"r");
        string content;
        char   buf[8192];
        int    bytesRead=0;
        int    bytesTotal=0;
        while((bytesRead=fread(buf,1,8192,file))==8192) {
            filter(buf,bytesRead);
            content.append(buf,bytesRead);
            bytesTotal += bytesRead;
        }
        if(bytesRead) {
            filter(buf,bytesRead);
            content.append(buf,bytesRead);
            bytesTotal += bytesRead;
        }
        fclose(file);
        cerr<<"done. ( " << bytesTotal <<" bytes )\n";
        cerr<<"adding to suffix tree ...\n";
        tree.addString(content);
        cerr<<"done.\n";
    }
    NodeT const* ans = tree.root();
    tree.eachLeaf(initInfo);
    LetsRock fun(c-1,ans);
    tree.dfs(fun);
    printPath(ans);
    cout<<endl;
    toc();
    return 0;
}

1. 我干了什么

我写了个程序，运行时内存占用峰值为 323 MB，耗时 6.582s，从 2,827,372 字节的《魔戒》全本中找出了不算空格、大小写敏感的情况下出现两次或更多的最长子串：

All that is gold does not glitter,

Not all those who wander are lost;

The old that is strong does not wither,

Deep roots are not reached by the frost.

 

From the ashes a fire shall be woken,

A light from the shadows shall spring;

Renewed shall be blade that was broken,

The crownless again shall be king.

耗时 7.022 秒，内存占用峰值 351 MB，从 3,872,493 字节的 sqlite 3.6.22 的合并 c 文件中找到了最长重复子串：(忽略空格)

.c****************//**************Beginfileos_common.h********************
****** *************//***2004May22****Theauthordisclaimscopyrighttothissou
rcecode.Inpla ceof**alegalnotice,hereisablessing:****Mayyoudogoodandnotevi
l.**Mayyoufindforgiv enessforyourselfandforgiveothers.**Mayyousharefreely,
nevertakingmorethanyougive.  *********************************************
*********************************** ****Thisfilecontainsmacrosandalittlebi
tofcodethatiscommonto**alloftheplatform-sp ecificfiles(os_*.c)andis#includ
edintothose**files.****Thisfileshouldbe#includedb ytheos_*.cfilesonly.Itis
nota**generalpurposeheaderfile.*/#ifndef_OS_COMMON_H_#de fine_OS_COMMON_H_
/***AtleasttwobugshaveslippedinbecausewechangedtheMEMORY_DEBUG* *macrotoSQ
LITE_DEBUGandsomeoldermakefileshavenotyetmadethe**switch.Thefollowingc ode
shouldcatchthisproblematcompile-time.*/#ifdefMEMORY_DEBUG#error"TheME
MORY_DEB UGmacroisobsolete.UseSQLITE_DEBUGinstead."#endif#ifdefSQLITE
_DEBUGSQLITE_PRIVATE intsqlite3OSTrace=0;#defineOSTRACE1(X)if(sqlite3OSTra
ce)sqlite3DebugPrintf(X)#de fineOSTRACE2(X,Y)if(sqlite3OSTrace)sqlite3Debu
gPrintf(X,Y)#defineOSTRACE3(X,Y,Z) if(sqlite3OSTrace)sqlite3DebugPrintf(X,
Y,Z)#defineOSTRACE4(X,Y,Z,A)if(sqlite3OST race)sqlite3DebugPrintf(X,Y,Z,A)
#defineOSTRACE5(X,Y,Z,A,B)if(sqlite3OSTrace)sqli te3DebugPrintf(X,Y,Z,A,B)
#defineOSTRACE6(X,Y,Z,A,B,C)\if(sqlite3OSTrace)sqlite3D ebugPrintf(X,Y,Z,A
,B,C)#defineOSTRACE7(X,Y,Z,A,B,C,D)\if(sqlite3OSTrace)sqlite3D ebugPrintf(
X,Y,Z,A,B,C,D)#else#defineOSTRACE1(X)#defineOSTRACE2(X,Y)#defineOSTRA CE3(
X,Y,Z)#defineOSTRACE4(X,Y,Z,A)#defineOSTRACE5(X,Y,Z,A,B)#defineOSTRACE6(X,
Y, Z,A,B,C)#defineOSTRACE7(X,Y,Z,A,B,C,D)#endif/***Macrosforperformancetra
cing.Norm allyturnedoff.Onlyworks**oni486hardware.*/#ifdefSQLITE_PERFORMAN
CE_TRACE/***hwti me.hcontainsinlineassemblercodeforimplementing**high-perf
ormancetimingroutines.* //**************Includehwtime.hinthemiddleofos_com
mon.h****************//******* *******Beginfilehwtime.h*******************
***********************//***2008May27 ****Theauthordisclaimscopyrighttothi
ssourcecode.Inplaceof**alegalnotice,hereisab lessing:****Mayyoudogoodandno
tevil.**Mayyoufindforgivenessforyourselfandforgiveo thers.**Mayyousharefre
ely,nevertakingmorethanyougive.*************************** ***************
******************************************Thisfilecontainsinlinea smcodefo
rretrieving"high-performance"**countersforx86classCPUs.*/#ifndef
_HWTIME_ H_#define_HWTIME_H_/***Thefollowingroutineonlyworksonpentium-clas
s(ornewer)proce ssors.**ItusestheRDTSCopcodetoreadthecyclecountvalueoutoft
he**processorandreturn sthatvalue.Thiscanbeusedforhigh-res**profiling.*/#i
f(defined(__GNUC__)||defined( _MSC_VER))&&\(defined(i386)||defined
(__i386__)||defined(_M_IX86))#ifdefined(__GN UC__)__inline__sqlite_uint64s
qlite3Hwtime(void){unsignedintlo,hi;__asm____volati le__("rdtsc"
:"=a"(lo),"=d"(hi));return(sqlite_uint64)hi<<32|
lo;}#elifdefined(_MS C_VER)__declspec(naked)__inlinesqlite_uint64__cdeclsq
lite3Hwtime(void){__asm{rdt scret;returnvalueatEDX:EAX}}#endif#elif(define
d(__GNUC__)&&defined(__x86_64__))_ _inline__sqlite_uint64sqlite3Hw
time(void){unsignedlongval;__asm____volatile__("r dtsc":"=A
"(val));returnval;}#elif(defined(__GNUC__)&&defined(__ppc__))
__inline__ sqlite_uint64sqlite3Hwtime(void){unsignedlonglongretval;unsigne
dlongjunk;__asm__ __volatile__("\n\1:mftbu%1\n\mftb%L0\n\mftbu%0\n\cm
pw%0,%1\n\bne1b":"=r"(retval) ,"=r"(junk));return
retval;}#else#errorNeedimplementationofsqlite3Hwtime()foryour platform./**
*Tocompilewithoutimplementingsqlite3Hwtime()foryourplatform,**youcan remov
etheabove#errorandusethefollowing**stubfunction.Youwilllosetimingsupportfo
r many**ofthedebuggingandtestingutilities,butitshouldat**leastcompileandru
n.*/SQLI TE_PRIVATEsqlite_uint64sqlite3Hwtime(void){return((sqlite_uint64)
0);}#endif#endi f/*!defined(_HWTIME_H_)*//**************Endofhwtime.h*****
********************** *******************//**************Continuingwherew
eleftoffinos_common.h******** **********/staticsqlite_uint64g_start;static
sqlite_uint64g_elapsed;#defineTIMER_ STARTg_start=sqlite3Hwtime()#defineTI
MER_ENDg_elapsed=sqlite3Hwtime()-g_start#de fineTIMER_ELAPSEDg_elapsed#els
e#defineTIMER_START#defineTIMER_END#defineTIMER_EL APSED((sqlite_uint64)0)
#endif/***IfwecompilewiththeSQLITE_TESTmacroset,thenthefo llowingblock**of
codewillgiveustheabilitytosimulateadiskI/Oerror.This**isusedfort estingthe
I/Orecoverylogic.*/#ifdefSQLITE_TESTSQLITE_APIintsqlite3_io_error_hit=0 ;/
*TotalnumberofI/OErrors*/SQLITE_APIintsqlite3_io_error_hardhit=0;/*Numbero
fnon -benignerrors*/SQLITE_APIintsqlite3_io_error_pending=0;/*Countdowntof
irstI/Oerro r*/SQLITE_APIintsqlite3_io_error_persist=0;/*TrueifI/Oerrorspe
rsist*/SQLITE_APIi ntsqlite3_io_error_benign=0;/*Trueiferrorsarebenign*/SQ
LITE_APIintsqlite3_diskfu ll_pending=0;SQLITE_APIintsqlite3_diskfull=0;#de
fineSimulateIOErrorBenign(X)sqli te3_io_error_benign=(X)#defineSimulateIOE
rror(CODE)\if((sqlite3_io_error_persist &&sqlite3_io_error_hit)\||
sqlite3_io_error_pending--==1)\{local_ioerr();CODE;}st aticvoidlocal_ioerr
(){IOTRACE(("IOERR\n"));sqlite3_io_error_hit++;if(!sqlite3_io _e
rror_benign)sqlite3_io_error_hardhit++;}#defineSimulateDiskfullError(CODE)
\if( sqlite3_diskfull_pending){\if(sqlite3_diskfull_pending==1){\local_ioe
rr();\sqlit e3_diskfull=1;\sqlite3_io_error_hit=1;\CODE;\}else{\sqlite3_di
skfull_pending--;\ }\}#else#defineSimulateIOErrorBenign(X)#defineSimulateI
OError(A)#defineSimulateD iskfullError(A)#endif/***Whentesting,keepacounto
fthenumberofopenfiles.*/#ifdefSQ LITE_TESTSQLITE_APIintsqlite3_open_file_c
ount=0;#defineOpenCounter(X)sqlite3_ope n_file_count+=(X)#else#defineOpenC
ounter(X)#endif#endif/*!defined(_OS_COMMON_H_) *//**************Endofos_co
mmon.h*******************************************//** ************Continui
ngwhereweleftoffinos_ 

正如之前在 后缀树的介绍 中说过的那样，俺想要弄出个能压缩 C 程序代码的工具，而上面的就是原型了：找出出现多次且较长的子串， #define 一下，重复多次，差不多了。

2. 怎么做的

有了后缀树，这样的工作可真是简单啊：

/*
 * Author  : If
 * Date    : Oct/14th/2010
 * Version : 0.0.1
 */
/*
Permission is hereby granted, free of charge, to any person or organization
obtaining a copy of the software and accompanying documentation covered by
this license  (the "Software")  to use,  reproduce,  display,  distribute,
execute, and transmit the Software, and to prepare derivative works of the
Software, and to permit third-parties to whom the Software is furnished to
do so, all subject to the following:

The copyright notices in the Software and this entire statement, including
the above license grant, this restriction and the following disclaimer,
must be included in all copies of the Software, in whole or in part, and
all derivative works of the Software, unless such copies or derivative
works are solely in the form of machine-executable object code generated by
a source language processor.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED,  INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE, TITLE AND NON-INFRINGEMENT. IN NO EVENT
SHALL THE COPYRIGHT HOLDERS OR ANYONE DISTRIBUTING THE SOFTWARE BE LIABLE
FOR ANY DAMAGES OR OTHER LIABILITY, WHETHER IN CONTRACT, TORT OR OTHERWISE,
ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
DEALINGS IN THE SOFTWARE.
*/

#include "suffixtree.h"
#include <algorithm>
#include <iterator>
#include <iostream>
#include <string>
#include <cmath>
#include <ctime>
using namespace std;

static void ticToc_(bool s)
{
    static clock_t start_ = clock();
    if(s) {
        start_ = clock();
    } else {
        clock_t end_=clock();
        std::cerr
            << (end_ - start_) << " ticks"
            << "    (" << (end_ - start_) * (1000.)/CLOCKS_PER_SEC <<"ms)"
            << std::endl;
    }
}

inline void tic()
{
    ticToc_(true);
}

inline void toc()
{
    ticToc_(false);
}


struct Info {
    int cv,depth,isLeaf;
    Info():cv(-1),depth(-1),isLeaf(0){}
};

typedef Node<char,Info> NodeT;

void initInfo(NodeT& node) {
    node.info.depth = node.depth + node.len;
    if(node.branches.empty()){
        node.info.isLeaf = 1;
        node.info.cv = node.leafNum;
    } else {
        node.info.isLeaf = 0;
        NodeT* p = node.branches[0];
        if(p->info.cv==-1) {
            initInfo(*p);
        }
        node.info.cv = p->info.cv;
    }
}

void printPath(NodeT const* node)
{
    if(node->parent!=node) {
        printPath(node->parent);
    }
    copy(node->str, node->str+node->len, ostream_iterator<char>(cout));
}

struct LetsHaveFun
{
    NodeT const*& result;
    LetsHaveFun(NodeT const*& root):result(root){}
    void operator()(NodeT& node){
        if(!node.info.isLeaf &&  // more than once
            node.depth != 0 &&   // not root
            node.info.depth > result->info.depth && // better
            abs(node.info.cv - node.branches.back()->info.cv) >=
                node.info.depth  // do not overlap
        ) {
            this->result = &node;
        }
    }
};

int main(int c,char**v) {
    if(c>2)
        return 1;
    SuffixTree<char, Info> stree;
    NodeT const* ans = stree.root();
    LetsHaveFun fun(ans);
    string source;
    if(c==2&&v[1][0]=='-') {
        if(v[1][1]=='S') // do not skip white space
            cin>>noskipws;
        else if(v[1][1]=='s')
            cin>>skipws;
        else
            return 1;
    } else {
        return 1;
    }

    copy(istream_iterator<char>(cin), istream_iterator<char>(),
         back_inserter(source));
    tic();
    stree.addString(source);
    stree.dfs(initInfo);
    stree.dfs(fun);
    printPath(ans);
    cout<<endl;
    toc();
}

3. Question

这次有问题顺便想要请教一下高人们，在上面的代码中有一段让我很不爽：

struct LetsHaveFun
{
    NodeT const*& result;
    ...

我的本意是想用 NodeT const* result ; 然而那么做的话 stree.dfs(fun) 这句话结束之后 fun.result 又回到了 root （LetsHaveFun::operator() 中 result 的确会变的！），百思不得其解，似乎碰到了某个语法的黑暗角落；然而在这个问题上 VC2008 和 GCC 4.5.0 竟然表现得出奇的一致以至于我开始怀疑自己了，谁来救救我？

4. PostScript

suffixtree.h 全部内容在我的 后缀树的介绍 中。

5. Update

Ubuntu 威武，同样的代码，同样的文件系统，同样的计算机配置，同样的编译器，同样的编译选项，在 Ubuntu 上面，此处(Win7)耗时 6.5 秒的程序变得只要 4.5 秒了，Astonishing