久久av无码专区亚洲av桃花岛,久久精品国产一区二区三区日韩,久久久久AV综合网成人

gdb��h��补全功能。功能键�?lt;TAB>。例如break�Q�在输入bre之后�?lt;TAB> 键，gdb��׃��补全为break。如果只输入b�Q�然后按�Q�gdb会响一壎ͼ��q�说明有多个以b开始的命��o。这�U�情况下再按一 ��?lt;TAB>�Q�gdb��׃��把所有以b开始的命��o输出出来。下面是此时的屏�q�截图：

如果只是想看一下以某个(�?字符开始的命��o�Q�可以按?�Q�而不用按两次。在�? �?lt;META>键的电脑上，可以�?lt;ESC>键代�ѝ��这个命令按��h��有点�ȝ��Q�比按两��?lt;TAB>要麻烦多了，如果不�?lt;TAB>键被按坏�Q�我��你还是按吧�?/p>

命��o补全可以用于gdb命��o�Q�gdb子命令，�E�序中的�W�号名（例如函数名等�Q��?/p>

在调试c++�E�序�Ӟ��基本上肯定会遇到的问题就是重载函数。例如，在设�|�断点的时候，假设有两个名为overload的函敎ͼ��q�时��Z��区分到底是那个函敎ͼ��需要加上函数参数类型（函数名加上参数列表作为逻辑上的一个词�Q�。�ؓ了��gdb能将参数列表两边的括号作��个词的一部分�Q�需要用单引�?��函数整个的括�v来。看下图�Q?/p>

获取帮助

启动gdb后，可以输入命��ohelp得到gdb的命令列表。注意的是这时输出的每个条目都是一�c�d��令。上个图�Q?

得到命��o�c�d��后，可以用命�?help class得到此类别的所有命令。上图：

上面的图中只昄��了部分breakpoints命��o�?/p>

其他跟帮助相关的命��o有：

a)help command

用于昄��命��ocommand的帮助信息�?/p>

b)apropos args

�q�里的args可以使正则表辑ּ�。显�C�所有匹配args的命令的��要说明�?/p>

c)complete args

昄��所有以args开始的命��o�?/p>

另外�q�有两个很有用的命��o�Q?info �?show �?/p>

a)info

用于昄��被调试程序的信息。例如传递到当前函数的参�?info args;或者查看当前寄存器的�?info registers;也可以查看断�?info breakpoints。可以用help info查看info的说明�?/p>

b)show

�q�个命��o用于昄��gdb的信息。也��是gdb的一些属性倹{��可以用help show查看帮助信息。这个命令通常应该是配合set用的�Q�用于设定gdb的属性）�?/p>

好了�Q�现在对gdb应该有个大概的认识了�Q�下面我们就要拿几个��例子来验证一些常用命令的效果。Let's go!

�?�C�Z��1

首先说明一点，要想高效的��用gdb的功能，需要在�~�译�E�序的时候要加上-g选项�Q�这个选项会把调试信息加到可执行文件中�?/p>

下面说一下示例文�Ӟ��包括三个�Q�gdb.h�Q?gdb.cpp�Q?test.cpp

gdb.h

#ifndef _GDB_H
#define _GDB_H 1

class gdb
{
public:
    explicit gdb(int v);
    void overload(int one);
    void overload(int one, int two);
    void catch_ex(int ex); //exception
    void loop();
private:
    int value;
    int array[10];
};

#endif

gdb.cpp

#include "gdb.h"
#include 
using namespace std;

gdb::gdb(int v)
{
    value = v;
    for(int i=0; i<10; i++)
    {
        array[i] = i;
    }
}

void gdb::overload(int one)
{
    cout<<"function overload with one parameter: "<}

void gdb::overload(int one, int two)
{
    cout<<"function overload with two paremeters: "<}

void gdb::loop()
{
    int loop_array[10];
    for(int i=0; i<10; i++)
    {
        loop_array[i] = i;
    }

    int v=3;
    v=3;
    v=4;
}

void gdb::catch_ex(int ex)
{
    int e = ex;
    try
    {
        if(e <= 0)
        {
            throw e;
        }
        else
        {
            cout<<"function catch_ex: "<        }
    }
    catch(int x)
    {
        cout<<"exception: "<    }
}

test.cpp

#include "gdb.h"

int main()
{
    gdb g(5);
    g.overload(1);
    g.overload(1, 2);
    g.loop();

    g.catch_ex(3);
    g.catch_ex(-1);

    return 0;
}

好了�Q�现在开始调试。首先启动gdb�Q�指定要调试的可执行文�g。前面已�l�说�q�了�Q�可以简单地使用gdb program来启动。或者可以首先启动gdb�Q�然后用file命��o指定要调试的文�g。下面是仅启动gdb后的画面�Q?

现在用file命��o指定要调试的文�g�Q?/p>

然后��可以用 run 或�?r 命��o来运行程序。在�q�行之前�Q�你可能需要�ؓ�E�序讑֮�一些信息，�q�些信息有一下四�U�：

1)�E�序参数

可以用set args命��o讑֮��E�序的参数。设定完后可以用show args查看讄��的是否正��。如果set args后面不带��M��参数�Q�则向程序传递的参数为空�?/p>

2)环境

�q�儿的环境就是在�pȝ��/用户配置文�g中设�|�的环境变量,像HOME, PATH之类�?GDB提供了在调试的时候改变这些变量值的方式,�q�样当需要的时候就不用退出gdb来重新设�|?GDB提供的命令有:

a) path directory �Q�－ ��?directory 加到环境变量PATH前面. 注意对PATH的改变只对调试的�E�序有效, GDB使用的PATH不会有改�?¹

b) show paths �Q�－昄��PATH的倹{�?/p>

c) show environment [varname] �Q�－昄��环境变量varname的��|��如果不指定varname�Q�则昄��所有环境变量的倹{�?/p>

d) set environment varname [= value] �Q�－讄��环境变量varname的��gؓvalue。这个改变只是对调试的程序生效。如果不提供value�Q�则��varname的值置为空�?/p>

e) unset environment varname �Q�－从环境中�U�除传递给�E�序的变量varname�?/p>

3)工作目录

在启动gdb调试�E�序的时候，被调试的�E�序会从gdb�l�承工作目录。当然gdb也提供了命��o来修改工作目录：

a) cd directory �Q�－ ��?directory 设�ؓ新的工作目录�?/p>

b) pwd �Q�－昄��当前工作目录�?/p>

4)标准输入输出

�q�没扑ֈ�在windows里面�q�个东西有啥用，现在也没有linux可用�Q�不好多说。有需要的自己看gdb手册吧。我��单抄一下手册吧�?/p>

在gdb中，可以��run命��o的输入输出重定向到文件或者其他终端。也可以通过tty命��o讄��被调试程序输入输出的讑֤�。命令格式是�Q?/p>

tty terminal 或�?set inferior-tty terminal.

tty ��是 set inferior-tty 的别名�?/p>

咚咚咚咚�Q�下面正式开始！

上面我们已经启动了程�? 也知道了如何�q�行�E�序。可是如果你直接执行run命��o会发玎ͼ��E�序直接�q�行�l�束了。如果你惛_��某一行或者某个函数调用的地方�Q�或者当某个变量/表达式的值改变的时候，也或者在某些事�g发生的时候－�Q�例如抛出异常、加载动态库�Q�或者创建子�q�程�Q�－的时候停止程序运行，那应该怎么办呢�Q?/p>

有了gdb�Q�一切就都好办了:), 利用下面�q�三个强大的武器�Q�你可以��L��的停止程序。小心了�Q�大家小心了�Q�偶要祭��三�g宝物了，它们是：

断点

断点��是指定一个位�|�，使得�E�序�q�行到这个位�|�的时候会停下来（当然�Q�还可以讄��条�g断点�Q�当�q�行到指定位�|�时�Q�只有满��了讄��的条�Ӟ��E�序才会停下来）�Q�这样便于观察程序的内部状态。断点相关的命��o主要有：

a)break location

在指定位�|?location 处设�|�断点，�q�里�?location 可以是函数名�Q�行��P��指��o地址�{�（关于如何指定 location ,可以�?a href="http://www.shnenglu.com/lucency/archive/2008/08/18/59214.html#location">�q�里�Q��?/p>

b)break

如果不指定�Q何参敎ͼ�break会在选定�?a href="http://www.shnenglu.com/lucency/archive/2008/08/18/59214.html#stack">栈��的下一条指令处讄��断点�?/p>

c)break ... if cond

讄��条�g断点。每�ơ到达断点的时候都会对表达�?cond 求��|��只有当结果�ؓ�?的时候程序才会在�q�个断点停下来�?/p>

d)tbreak args

讄��一个只生效一�ơ的断点。args跟break命��o里的参数意义相同�Q�也��是��_��可以为location�Q��ؓ�I�，或者条�Ӟ��?/p>

e)hbreak args

讄��g断点�?/p>

f)thbreak args

讄��只生效一�ơ的��g断点�?/p>

g)rbreak regex

在所有匹配正则表辑ּ� regex 的函��C��讄��断点�?/p>

h)info breakpoints [n]

i)info break [n]

j)info watchpoints [n]

上面三个命��o都是列出当前的断炏V��观察点和捕捉点�Q�如果指定参数n�Q�则仅列出第n个的信息�?/p>

来试验一把吧。首先用gdb启动�E�序�Q�假设我们想在test.cpp�?g.overload(1) �q�一行添加一个断点，那就执行命��o�Q�b test.cpp:6,执行完后�Q?/p>

�q�时可以用info break�{�命令查看断点信息：

然后我们�q�行�E�序�Q�看看有什么效果�?/p>

看到了吧�Q�程序停在了断点所在的行。这时可以用where或者frame查看当前的栈帧信息，也可以用 print 查看一些变量或者表辑ּ�的信息，或者info args查看参数信息�Q�等�{��?/p>

其他的命令大家可以自己尝试一下�?/p>

有时候我们�ƈ不确定要在哪里加断点�Q�例如当我们惛_��某个变量被改变或者被诅R��被写的时候让�E�序停下来，可能�׃��讉K��变量的地�Ҏ��较多�Q�要��x��个地斚w��加上断点比较�ȝ��Q�而且很可能有遗漏�Q�这时候我们就需要依赖另一个强大的命��o了，也就是观察点�?/p>

观察�?/h3>
观察�Ҏ��一�cȝ��D�的断点�Q�如果针�Ҏ��个变量或者表辑ּ�指定一个观察点�Q�那么当它们的��D��?写的时候，gdb会停止程序的执行。你不需要像讄��断点旉��h��指定这个观察点在程序中的位�|�。观察点相关的命令有�Q?/p>
a)watch expr [thread threadnum]

�?expr 讄��一个观察点。当 expr 的��D��改变的时候，gdb会停止程序的�q�行�?/p>

如果指定了线�E�参数thread threadnum �Q�则只有在线�E?threadnum 改变 expr 的值时�Q�程序才会停止�?/p>

b)rwatch expr [thread threadnum]

�?expr 讄��一个读观察炏V��当�E�序�?expr 的值时�Q�gdb会停止程序的�q�行�?/p>

c)awatch expr [thread threadnum]

�?expr 讄��一个访问观察点。当�E�序��L��者写 expr �Ӟ��gdb会停止程序的�q�行�?/p>

d)info watchpoints

昄��所有的断点、观察点、捕捉点。跟info break 相同�?/p>

下面再来看看观察点的使用�?/p>
首先我们讄��一个断点在g.loop()�q�一行，然后�q�行到这里。step�q�入loop()函数。这一串命令的执行如下�Q?/p>

�q�时我们已经�q�入loop()函数�Q�现在我们设�|�几个观察点。设�|�命令序列和讄��完后的效果如��：

可以看到�?个停止点�Q�其中前两个是我们设�|�的断点�Q�后面三个是观察炏V��分别�ؓwatch, rwatch �?awatch。另外还有一个地方就是，x86上默认是��g观察炏V�?/p>
好了�Q�来�q�行一下试试�?/p>

到达�W�一个观察点的时候程序停止运行，同时打印��Z��变量的旧值和新��|��以及观察点的位置�?/p>
下面我们接着�q�行�Q�看看遇到后面的观察点的时候又会怎样�?/p>

�E�序在第三个观察点停了下来（�W�二个观察点��观察点）�Q�同��h��印出了变量的新旧值和观察点的位置。第二个观察点由于是读观察点�Q�而程序中没有读这个变量的地方�Q�因此运行的时候被跌��了。�ؓ了看一下读观察点的效果�Q�我们再讄��一个读观察点：

i是��@环内的�P代器�Q�它会被复制�l�loop_array[i]变量�Q�也��是会被诅R��可以看刎ͼ��E�序会停止运行，输出i的倹{��注意：每次对i的读操作都会使得�E�序停止。下面是两次执行continue命��o后的输出�Q?/p>

观察点的内容差不多就�q�些了。另外有个需要注意的地方��是: watch命��o讄��的观察点只有在变量或者表辑ּ�的��D��改变得时候才会��得程序停止运行，如果只是被写�Q�但是值没有改变，则程序不会停止�?/strong>

上面已经讲了断点、观察点�Q�而对于某些情况，�q�两�U�停止点�q�不是最有效的方式。例如想在c++�E�序中跑出异常的时候停止程序，�q�时候用断点��׃��够有效了�Q�因为程序中可能好多异常处理的地方，如果一个个讄��断点�Q�那��太�ȝ��了（当然如果只处理某几个异常�Q�用断点也无不可�Q? 甚至用�v来更灉|��Q�；而观察点��更不可用了�?/p>
�q�种情况��需要用到捕捉点了�?/p>
捕捉�?/h3>
捕捉点也是一�cȝ��D�的断点�Q�它可以使得�E�序在某�U�事件发生时停止�q�行�Q�例如c++异常�Q�或者加载动态库、创建子�q�程�{�。设�|�捕捉点的命令是catch.

catch event

其中 event 可以是：

a)throw

c++抛出异常�?/p>

b)catch

c++捕捉异常�?/p>

c)exception

Ada异常�?/p>

d)exception unhandled

�E�序中未处理的异常�?/p>

e)assert

��p�|的Ada断言�?/p>

f)exec

对exec的调用（只在HP-UX和GNU/Linux中可用）�?/p>

g)fork

对fork的调用（只在HP-UX和GNU/Linux中可用）�?/p>

h)vfork

对vfork的调用（只在HP-UX和GNU/Linux中可用）�?/p>

i)load

动态加载共享库�Q�只在HP-UX中可用）�?/p>

j)load libname

动态加载共享库 libname �Q�只在HP-UX中可用）�?/p>

k)unload

卸蝲已加载的�׃�n库（只在HP-UX中可用）�?/p>

l)unload libname

卸蝲已加载的�׃�n�?libname �Q�只在HP-UX中可用）�?/p>

�q�有一个设�|�只生效一�ơ的捕捉点的命��o是： tcatch event �?/p>
下面再看一下捕捉点的��用�?/p>
首先在vtest.cpp�?g.catch_ex(-1); 讄��一个断点，然后�q�行�Q�进入此函数�?/p>

现在我们讄��一个捕捉点。��l�运行：

可以看到�E�序在抛出异常的地方停止了�?/p>

删除断点

当断点不再需要了�Q�那��应该删除掉�Q�否则每�ơ执行到断点的位�|�程序都要停下来�Q�会把�h逼疯的。删除断点的命��o有两个：clear和delete�?/p>
a)clear [ location ]

如果不指�?location �Q�则删除选择的栈帧中下一条要执行的指令上的�Q何断炏V��如果选择的是最内部的栈帧（也就是当前正执行的函数的栈��Q�，则clear会将刚刚使程序停止的断点被删除�? 关于 location 的说明可以看�q�里�?/p>

b)delete [breakpoints] [ range ... ]

删除指定范围 range 那的所有的断点、观察点、捕捉点。如果不指定参数 range �Q�则会删除所有的停止炏V��这里的 range 指定的是断点�~�号区间。可以用info break查看断点信息�?/p>

��用断点

如果不想删除断点�Q�只是想暂时使它失效�Q�则可以使用disable命��o。disable命��o的�Ş式如下：

a)disable [breakpoints] [ range ...]

使指定区�?range 内的断点失效。如果不指定 range �Q�则所有的断点都失效�?/p>

使断点生效的命��o是enable�Q��Ş式有�Q?/p>
a)enable [breakpoints] [ range ...]

使指定区�?range 内的断点或者所有断点生效�?/p>

b)enable [breakpoints] once range...

使指定区间内的断点生效一�ơ�?/p>

c)enable [breakpoints] delete range...

使指定区间内的断点生效一�ơ，然后删除�?/p>

断点条�g

断点条�g使得只有在相应的条�g满��Ӟ��断点才有效。这里的条�g表达式跟�E�序所用语�a�的逻辑表达式的语法相同�Q�例如在c/c++语言里，可以�?a==b 或�?x&&y�q�种表达式�?/p>
断点条�g可以在设�|�断点的时候指定，也可以在断点讄��后通过condition命��o来设�|�或者改变�?condition的�Ş式�ؓ�Q?/p>
a)condition bnum expression

讄��表达�?expression 为停止点 bnum 的条件�?/p>

b)condition bnum

删除停止�?bnum 的条件�?/p>

�q�有一个命令，可以使得gdb忽略断点的条件一定的�ơ数�Q�其形式为：

a)ingore bnum count

指定位置

许多gdb命��o都接受一个用于指定程序位�|�的参数。位�|�的指定方式有下面几�U�：

a) linenum

当前源文件的行号�?/p>

b) -offset

当前行前面，跟当前行间隔�?offset 的行。当前行可以�q�样��定�Q��用list命��o�Q�打印出来的最后一行就是当前行�Q�或者对于断点命令，选定的栈帧中�Q�程序停止执行的位置��是当前行�?/p>

c) +offset

当前行后面，跟当前行间隔�?offset 的行�?/p>

d) filename:linenum

源文�?filename 中的�?linenum�?/p>

e) function

当前源文件中的函�?function�?/p>

f) filename:function

源文�?filename 中的函数 function�?/p>

g) * address

指定�E�序地址 address。常用的 address 形式有：

expression �Q�－当前语言中有效的表达式�?/p>

funcaddr �Q�－函数的地址。在c/c++中就是函数名�?/p>

'filename'::funcaddr �Q�－源文�?filename 中的函数地址 funcaddr�?/p>

后面懒得写了�Q�暂时先放一放。发现就��是抄文档，内容多了也是个很累�h的活。唉�Q�懒了，不行�?..

�?/h3>
待添�?/p>

数据

待添�?/p>

�?�C�Z��2

待添�?/p>

�?后记

�q�篇文章只是捡了GDB中最常用的一些东西，而且�q�只是最常用的东西中的一��部分，有兴��或者需要的可以直接看GDB的文档，可以�?a >�q�里扑ֈ��?/p>

1. 不知道是不是因�ؓwindows和linux�pȝ��的不同，用gdb启动�E�序后，执行show paths后输出：Executables and object file path: 。也��是说输出的值是�I�的�?/p>

季阳 2008-08-18 13:31 发表评论

Suffix Trees[译]

季阳 — Sat, 12 Jul 2008 02:44:00 GMT
�q�两天看了下后缀树的介绍,发现一��文�?讲得挺清楚的,��q��译了�?希望对大家有帮助.原文章在�q�儿
希望原作者不要找我麻烦哈。如果有啥版权问题，我马上删掉。也因此�Q?font color="#cc0000">此文暂时��止转蝲。此中文版如果有版权,归本人所�?

我英语本来就不咋圎ͼ�有些地方肯定比较生硬或者有误，�Ƣ迎指正�?br>
��Z��贴个自己的代码，只是一个简单的实现�Q�没有考虑效率问题。如果想要更成熟�E�_��的，可以看这�?/a>�?br>
再顺个便抱怨两句。文章中囄��要是多点�Q�发布的时候还真是�ȝ��Q�要一个个插入才行。用ScribeFire发布好像也不能直接上传图片（也可能是我不会）�?br>
Data Structures, Algorithms, & Applications in Java
Suffix Trees
Copyright 1999 Sartaj Sahni

你看见过�q�个字符串吗?(Have You Seen This String?)

在经典的子串查找问题�?�l�定一个字�W�串S和模式P,查找P在S中是否存�?例如,模式P = cat在字�W�串S1 = The big cat ate the small catfish存在(两次),但是不在字符串S2 = Dogs for sale�?

人类基因�l�计划的研究者者经常要基因数据�?-其中包含��C��万计的基�?-中查�?font color="#3333ff">子串/模式(�q�里�?font color="#3333ff">子串�?font color="#3333ff">模式可以�怺�替代使用).每个基因由字�W�集{A,C,G,T}中的字符构成的序列或者说字符串表�C?但是,基因库里的大部分字符串长度大�U?font color="#3366ff">2000个字�W?�q�有一些有��C��万计的字�W?考虑到基因库的大��和子串查找的频�?一个尽可能快的用来从基因库的字�W�串中查扑֭�串的��法是很必要�?

我们可以使用在标准的��法教科书中描述的模式匹配算法在字符串S中查找模式P.�q�个��法的复杂度�?font color="#3366ff">O(|P| + |S|), �q�里�?font color="#3366ff">|P|表示P的长�?例如字符(letter)或数�?digit)的个�?.当考虑到模式P可能出现在S中的��M��位置�?�q�个复杂度看��h��是很好的.因此,在得出P不在S中存在前,我们必须��试S的每�?font color="#3366ff">字符(letter)/数字(digit)(�q�里的术语字�W�和数字意义相同。译注：后面会统一��译为字�W?.更进一�?在我们得出模式在字符串中出现�?我们必须��试模式的每个字�W?因此,每个字符串查扄��法消耗的旉��是P和S长度的线性函�?

当用�l�典的字�W�串匚w��法在S中查扑֤�个模�?font color="#3366ff">P1,P2,...,Pk�?消耗的旉��?font color="#3366ff">O(|P1| + |P2| + ... + |Pk| + k|S|)(因�ؓ查找Pi消耗的旉��?font color="#3366ff">O(|Pi| + |S|)).我们马上要学习的后缀树结构能��复杂度减少�?font color="#3366ff">O(|P1| + |P2| + ... + |Pk| + |S|).此时的O(|S|)用于为S创徏后缀�?查找每个模式只需要花费O(|Pi|)的时�?在S的后�~�树创建完成之�?.因此,一旦S的后�~�树创建完�?查找每个模式需要的旉��军_��于模式的长度.

后缀�?br>
字符串S�?strong>后缀�?/strong>实际上是S的所有非�I�后�~�的压�~�trie�?因此我们有时��后�~�树称为trie,��它的子树称为subtrie.�Q�不清楚trie树的可以�?a >�q�里或�?a target="_blank" >�q�里�Q?br>
字符�?/small>S=peeper的非�I�后�~��?font color="#3366ff">peeper,eeper,eper,per,er和r.因此字符串peeper的后�~�树是包含元素(�q�些元素也是关键�?peeper,eeper,eper,per,er和r的压�~�trie�?字符串peeper的字�W�集�?font color="#3366ff">{e,p,r}.因此,压羃trie树的基数(radix)�?.如果需�?我们可以用映��?font color="#3366ff">e -> 0, p -> 1, r -> 2��字�W�串的字�W��{换�ؓ数字.�q�种转换只有在我们��用一�U�节点结�?-每个节点有一个包含子节点指针的数�l?-才需�?�?展示了peeper后缀的压�~�trie�?带有变信�?.�q�棵压羃trie树也是字�W�串peeper的后�~��?

Figure 1 Compressed trie for the suffixes of peeper

�׃��信息节点(译注:也就是叶节点)D-I中的数据是peeper的后�~�,每个信息节点只需要保存它所表示的后�~�在字�W�串中的起始索引.当我们从1开始从左到右烦引peeper中的字符�?信息节点D-I只需要保存烦�?font color="#3366ff">6,2,3,5,1�?font color="#3366ff">4卛_��.利用保存在信息节点中的烦�?我们可以讉K��S的后�~�.�l�果如图2所�C��?br>

Figure 2 Modified compressed trie for the suffixes of peeper

每个分支节点的第一个字�D�|��C��其�ؓ根的subtrie中元�?译注:应该是指子节�?的引�?我们可以用被引用的元素的首字�W�的索引代替元素引用.�?展示了替换后的树.我们��会用这�U�修改后的�Ş式作为后�~�树的表示.

Figure 3 Suffix tree for peeper

如果后缀树的每条边用从分支节点到其子节点的字�W?�?标注,可以更容易描�q�后�~�树的查找和构建算�?标签的第一个字�W�用来确定要�U�d��哪一个子节点,剩余的字�W�表�C��跌��的字�W?�?.�?展示的就是图3用这�U�方式画出后得到的后�~��?

Figure 4 A more humane drawing of a suffix tree

在后�~�树的更直观的��L��?从�Q意根节点��C��息节点的路径上所有边的标�{�拼接在一起得到的��是信息节点表示的后�~�.When the digit number for the root is not 1, the humane drawing of a suffix tree includes a head node with an edge to the former root. This edge is labeled with the digits that are skipped over.

后缀树的某个节点表示的字�W�串是由根节点到此节点的路径上的标签拼出来的.�?中的节点A表示�I�Z��epsilon,节点C表示字符串pe,节点F表示字符串eper.

�׃��后缀树的关键字长度不�?我们必须保证没有一个关键字是另一个的真前�~�(proper prefix).当字�W�串S的最后一个字�W�在S中只出现一��?��׃��会出现S的其中一个后�~�是另一个后�~�的真前缀的情�?在字�W�串peeper�?最后的字符是r,�q�且只出��C��一��?因此peeper的后�~�中就不会出现真前�~�的情�?字符串data的最后字�W�是a,�q�且出现了两��?因此,data有两个以a开始的后缀,ata和a.后缀a是ata的真前缀.

当字�W�串S的最后字�W�在S中出现多于一��?��必��d��S的所有后�~�后面附加一个新的字�W?比如�?),�q�样��M��一个后�~�都不会是其他后缀的前�~�.�q�有一�U�方法是,我们可以在S后面附加新的字符#,得到新的�?#,然后创徏$#的后�~��?�q�样做之后得到的后缀树比直接在S的每个后�~�后面附加#会多一个后�~�#.

让我们查��N��个子串吧
但是�Q�首先要说明几个术语
�?font color="#3366ff">n=|S|表示要创建后�~�树的字符串的长度.我们从左到右依次�l�S的字�W�编�?最左边的编号�ؓ1.S[i]表示S的第i个字�W?suffix(i)表示从字�W�i开始的后缀S[i]...S[n],1<=i<=n.

关于查找
当在S中查找模式P�?用到的一个基本的观察(observation)是P在S中出现当且仅当P是S的某个后�~�的前�~�.

假设P = P[1]...P[k] = S[i]...S[i+k-1].则P是suffix(i)的前�~�.既然suffix(i)在我们的压羃trie树中(也就是后�~��?,我们可以利用在压�~�trie树中查找关键字前�~�的策略来查找P.

让我们在字符�?font color="#3366ff">S=peeper中查找模�?font color="#3366ff">P=per.假设我们已经为S创徏好了后缀�?�?).查找从根�l�点A开�?因�ؓP[1]=p,我们��着标签以p开始的�?当顺着此边�l�箋�?我们对边标签的剩余字�W�和P的后�l�字�W�做比较.�׃��标签的剩余字�W�跟P的字�W�相�W?我们到达分支C.在到达C的过�E�中,我们已经使用了P的前两个字符.�W�三个字�W�是r,因此我们从节点C��着以r开始的边��l?�׃��q�条�Ҏ��有其他字�W?因此不需要其他比�?到达信息节点I.�q�时,P中的字符已经用完�?我们��断定P在S�?�׃��已经到达信息节点I,我们断定P实际上是S的后�~�.在实际的后缀树表�C�Z��(而不是如�?�q�种人性化的表�C?,信息节点I包含索引4,�q�告诉我们模式P=per由S=peeper的第4个字�W�开�?也就是说,P=suffix(4)).更进一�?我们可以得到P在S中只出现一��?如果一个模式在字符串中出现多次,查找会在分支节点中止,而不是信息节�?(译注:例如查找pe,查找在节点C中止,说明它在S中出��C��两次--C有两个叶子节�?

现在我们来查找模�?font color="#3366ff">P=eeee.�q�是从根�l�点开�?�׃��P的第一个字�W�是e,我们沿着以e开始的边到达B.下一个字�W�还是e,因此我们从B开始沿着以e开始的边��l?在沿着�q�条边向下的�q�程�?我们需要比较边标签的剩余字�W�per和P的剩余字�W�ee.比较�W�一对字�W?p,e)时无法匹�?因此我们断定P不在S�?

假设我们查找模式P=p.从根开�?沿着以p开始的边往�?在向下的�q�程�?我们比较边的剩余字符(只有字符e)和模式的剩余字符.�׃��已经到P的结��?我们断定P是以节点C为根的subtrie的所有关键字的前�~�.可以通过遍历以C为根的subtrie、访问subtrie的所有信息节�Ҏ��到P出现的所有位�|�。如果只需要P出现的一个位�|�，可以利用存储在节点C的第一部分的烦引。当沿着到节点X的边查找时模式结束，我们��p��已到达节点X�Q�查扑֜�节点X�l�束�?br>
当查找模�?font color="#3366ff">P=rope�Q�利用P的第一个字�W�r到达信息节点D。由于模式还没有�l�束�Q�我们必��L��据D的字�W�检查P的剩余字�W�。检查显�C�P不是D的关键字的前�~��Q�因此P不在S=peeper中�?br>
我们要做的最后一个查找是�Ҏ��式P=pepe。从�?的根�l�点开始，我们沿着以p开始的边到达节点C。下一个未��查的字符是p。因此，从C开始，我们希望沿着以p开始的边��l�。由于没有满��个条件的边，我们断定pepe不在peeper中�?br>

Other Nifty Things You Can Do with a Suffix Tree

一旦�ؓ字符串S创徏好了后缀树，我们��可以在O(|P|)旉��内判断S是否包含P。这意味着如果��士比亚的戏剧“�|�密�Ƨ与�׃��?#8221;的内容创��Z��后缀树，我们��可以非常快的判断文章中是否存在短语wherefore art thou。事实上�Q�只需话费比较18个字�W�的旉��Q�模式的长度�Q�。查找时间跟文章的长度无兟�?br>
其他可以快速完成的有趣事情�Q?br>
1.查找模式P的所有出现。这是通过对P查找后缀树实现。如果P臛_��出现一�ơ，查找会在信息节点或者分支节点中止。当中止于信息节�Ҏ��Q�P只出��C��ơ。如果中止于分支节点X�Q�模式出现的所有地方可以通过讉K��以X为根的subtrie的信息节�Ҏ��得到。如果我们按照下面的方式�Q�这个访问操作可以在O(n)�Q�n是模式出现的�ơ数�Q�时间内完成�?br>
(a)
��所有的信息节点按照节点所表示的后�~�的字典序链�v来（�q�也是从左到��x��描信息节�Ҏ��遇到�q�些节点的顺序）。图4的信息节点会按照E,F,G,H,I,D的顺序链接�v来�?br>
(b)
在每个分支节点内�Q�保存以此节点�ؓ根的subtrie的第一个和最后一个信息节点的引用。图4中节点A,B和C分别保存序对(E,D),(E,G)�?H,I)。我们用序对(firstInformationNode, lastInformationNode)周游以firstInformationNode开始、以lastInformationNode�l�束的链。这个周�怼�得到模式P出现的所有位�|�。注意，当我们在分支节点中保存序�?firstInformationNode, lastInformationNode)�Ӟ��׃��需要再保存到subtrie中的信息节点的引用（也就是字�D�element�Q��?br>
2.查找包含模式P的所有字�W�串。假设我们有一些字�W�串S1,S2,... Sk�Q�我们想得到所有包含P的字�W�串。例如，基因库中包含��C��万计的字�W�串�Q�当一个研�I�员提交一个查询字�W�串�Q�我们就要报告所有包含此模式的字�W�串。�ؓ了有效的执行�q�类查询�Q�就需要创��Z��个包含字�W�串S1$S2$...$Sk#的所有后�~�的压�~�trie树（也称为多字符串后�~�树）�Q�这里的$,#是两个不在字�W�串S1, S2, ..., Sk中出现的不同字符。在后缀树的每个�Q�分支）�l�点N中，保存所有的字符串Si的链表，其中Si是以N为根的subtrie中所有的信息节点表示的字�W�串的开始点位于其中的字�W�串�Q�译注：真拗口啊�Q�这儿的意思就是对某个信息节点L�Q�如果L表示的字�W�串从Si的某个位�|�开始，那就��Si的引用放到L的父辈节点的链表中）�?br>
3.查找S中出现次数至��ؓm>1�ơ的子串。这个查询可以按照下面的方式在O(|S|)旉��内完成：
(a)周游后缀树，�Ҏ��个分支节点X�Q�保存从根节点到X节点的字�W�串的长度l和以X为根的subtrie中信息节点的数目m�?br>(b)周游后缀树，讉K��信息节点�?gt;=m的分支节炏V��l最大的分支节点表示的就是出现次�?gt;=m的最长子丌Ӏ?br>
注意步骤(a)只需要执行一�ơ。完成后�Q�我们可以对需要的��L��m执行步骤(b)。另外还要注意，当m=2是，不需要确定subtrie中信息节点的数目。在后缀树中�Q�每个分支节点之后有两个信息节点�?br>
4.查找字符串S和T的最长公共子丌Ӏ�这可以按照下面的方式在O(|S|+|T|)旉��内完成：
(a)为S和T创徏多字�W�串后缀树（也就�?font color="#3366ff">S$T#的后�~�树）
(b)周游后缀树，查找表示的字�W�串最长，�q�且以其为根的subtrie的信息节点表�C�的字符串中�Q�至��有一个从S开始，另一个从T开始的字符丌Ӏ?br>
注意�Q�有个相关的查找S和T的最长公共子序列的问题用动态规划算法在O(|S|*|T|)旉��内完成�?br>
如何创徏你自��q��后缀�?/font>
三个观察(observation)
��Z��更有效的创徏后缀树，我们为每个分支节�Ҏ��加字�D�longestProperSuffix。表�C�非�I�字�W�串Y的分支节点的longestProperSuffix字段指向表示Y的最长真后缀的分支节点（Y的最长真后缀通过��L��Y的首字符得到�Q�。根�l�点的longestProperSuffix未��用�?br>
�?表示的是�l�图4加上最长真后缀指针后得刎ͼ��l�常��最长真后缀指针��U�Cؓ后缀指针�Q�。后�~�指针用红色箭头表�C�。节点C表示字符串pe。pe的最长后�~�e��p��点B表示。因此C的后�~�指针指向B。e的最长后�~�是空丌Ӏ�由于根�l�点A表示�I�Z��Q�因此B的后�~�指针指向A�?br>

Figure 5 Suffix tree of Figure 4 augmented with suffix pointers

观察1 如果S的后�~�树有一个表�C�字�W�串Y的分支节点，那么后缀树中也有一个表�C�Y的最长后�~�Z的分支节炏V�?br>证明设P��C�Y的分支节炏V��由于P是分支节点，臛_��有两个不同的字符x和y�Q��得S中有两个分别以Yx和Yy开始的后缀。因此，S有两个分别以Zx和Zy开始的后缀。因此，S的后�~�树中必然有一个对应Z的分支节炏V�?br>
观察2 如果S的后�~�树有一个表�C�Y的分支节点，那么树中对Y的每个后�~�都有一个对应的分支节点�?br>证明 ��p��?卛_��得到�?br>
注意�?中有一个表�C�pe的分支节炏V��因此，树中一定有表示e和epsilon的分支节炏V�?br>
在描�q�后�~�树的创徏��法�Ӟ��有两个概念很有用�Q?font color="#3366ff">last branch node�?font color="#3366ff">last branch index。后�~�suffix(i)的last branch node是表�C�suffix(i)的信息节点的父节炏V��在�?中，suffix(1)...suffix(6)的last branch node分别是C,B,B,C,B和A。对��L��后缀suffix(i)�Q�其last branch index lastBranchIndex(i)是在suffix(i)的last branch node中，产生分支的字�W�的索引。在�?中，lastBranchIndex(1)�Q?,因�ؓ�Q�suffix(1)=peeper�Q�suffix(1)�׃��息节点H表示�Q�H的父节点是C�Q�C的分支是在suffix(1)的第三个字符产生的；suffix(1)的第三个字符是S[3]。可以验证一下，lastBranIndex[1:6] = [3,3,4,6,6,6]�?br>
观察3 在S的后�~�树中�Q?lastBranchIndex(i) <= lastBranchIndex(i+1), 1 <= i < n�?br>证明作�ؓ�l�习�?br>
Get Out That Hammer and Saw, and Start Building

��Z��创徏你自��q��后缀树，你必��ȝ��你自��q��字符串开始。我们��用R = ababbabbaabbabb来阐�q�后�~�树的构徏�q�程。由于R的最后字�W�b出现了不止一�ơ，我们在R后面附加字符#�Q��ؓ新的字符串S=R#创徏后缀树�?br>
创徏�{�略
后缀树的创徏��法从表�C�空串的根结点开始。根�l�点是一个分支节炏V��创建后�~�树过�E�的��M��时候，都有一个分支节点被指定位活动节�?active node)。这是插入下一个后�~�的�v始节炏V��用activeLength表示根结点对应的字符串的长度。开始时�Q�根节点是活动节点，activeLength=0。图6展示了开始时的状态，�l�色的节�Ҏ��z�d��节点�?br>

Figure 6 Initial configuration for suffix tree construction

随着处理的进行，我们会不断往树中��d��分支节点和信息节炏V��新��d��的分支节点用品红色表�C�，新添加的信息节点用青色表�C�。后�~�指针为红艌Ӏ?br>
后缀按照suffix(1), suffix(2), ..., suffix(n)的顺序依�ơ插入到树中。后�~�以这�U�顺序插入是通过从左到右扫描字符串S的方氏完成。用tree(i)表示插入后缀suffix(1), ..., suffix(i)之后形成的树�Q?font color="#3366ff">lastBranchIndex(j, i)表示tree(i)中后�~�suffix(j)的last branch index�?font color="#3366ff">minDistance表示从活动节点到卛_��插入的后�~�的last branch index的距��ȝ��下界�Q�译注：感觉�q�个东西在实现的时候没啥意义）。开始时�Q�minDistance = 0�q�且lastBranchIndex(1,1) = 1。当插入suffix(i)�Ӟ��满��条�glastBranchIndex(i,i) >= i + activeLength + minDistance�?br>
��Z��向tree(i)中插入suffix(i+1)�Q�我们必��遵循如下步骤：
1.��定lastBranchIndex(i+1, i+1)。�ؓ了完成这点，我们从当前活动节点开始。新后缀的开始的activeLength个字�W�（也就是字�W�S[i+1], S[i+2], ..., S[i + activeLength]�Q�已知是跟当前活动节点表�C�的字符串相匚w��的。因此，��Z��定lastBranchIndex(i+1,i+1)�Q�需要检��新后缀的activeLength + 1, activeLength + 2, ...字符。这些字�W�用于确定tree(i)中进一步处理时要经�q�的路径�Q�此路径始于�z�d��节点�Q�当lastBranchIndex(i+1,i+1)��定时中止。根据已知的lastBranchIndex(i+1,i+1) >= i + 1 + activeLength + minDistance�Q�这个过�E�可以简化，从而得到效率提升�?br>
2.如果tree(i)中没有表�C�字�W�串S[i]...S[lastBranchIndex(i+1,i+1)-1]的节点X�Q�则创徏一个�?br>
3.为suffix(i+1)��d��一个信息节炏V��这个信息节�Ҏ��X的孩子，从X��C��息节点的边上的标�{�是S[lastBranchIndex(i+1, i+1)]...S[n]�?br>
回到例子
我们从向�?中的树tree(0)插入suffix(1)开始。根�l�点是活动节点，activeLength = minDistance = 0。suffix(1)的第一个字�W�是S[1]=a。从tree(0)的活动节点开始没有以a开始的边（事实上，此时�z�d��节点没有��M��边）。因此，lastBranchIndex(1,1) = 1。我们创��Z��个新的信息节点和一条边�Q�边的标�{�是整个字符丌Ӏ�图7展示了结果tree(1)。根�l�点依然是活动节点，activeLength和minDistance没有变化�?br>

Figure 7 After the insertion of the suffix ababbabbaabbabb#

在我们的��L��中，信息节点的入边的标签标记为i+�Q�i表示标签在S中的开始位�|�，+表示标签一直到字符串的�l�尾。因此，在图7中，1+表示字符串S[1]...S[n]。图7也展�C�Z��字符串S。新插入的后�~�用青色表�C��?br>
��Z��插入后缀suffix(2)�Q�我们再�ơ从根结点开始检查后�~�的activeLength + 1 = 1, activeLength + 2 = 2, ...,字符。因为suffix(2)的第一个字�W�是S[2]=b�Q�活动节�Ҏ��有以S[2]=b开始的边，所以lastBranchIndex(2,2) = 2。因此我们创建新的信息节点和标记�?+的边。结果如�?所�C�。根�l�点依然是活动节点，activeLength和minDistance依旧没有变化�?br>

Figure 8 After the insertion of the suffix babbabbaabbabb#

注意�?是关于suffix(1)和suffix(2)的压�~�trie树tree(2)�?br>
下一个后�~�suffix(3)开始于S[3]=a。由于tree(2)的活动节�Ҏ��一个以a开始的边，所以lastBranchIndex(3,3) > 3。�ؓ了确定lastBranchIndex(3,3)�Q�必需要查看suffix(3)的更�q�字�W�。尤其是�Q�我们需要查看尽可能多的字符�Q�以便区分suffix(1)和suffix(3)。首先比较后�~�的第二个字符S[4]=b和边1+的第二个字符S[2]=b。由于S[4]=S[2]�Q�必��d��q�一步的比较。下一步比较S[5]和S[3]。由于这两个字符不同�Q�我们可以确定lastBranchIndex(3,3)�?。这�Ӟ��我们需要更新minDistance�?.注意�Q�因为lastBranchIndex(3,3) = 5 = 3 + activeLength + minDistance�Q�这是minDistance的最大可能倹{�?br>
��Z��插入suffix(3)�Q�我们将tree(2)的边1+一分�ؓ二。第一条边的标�{�是1,2;�W�一条边的标�{�是3+。这两个边之间插入新的分支节炏V��另外，�q�要为新插入的后�~��d��信息节点。结果如�?所�C�。边标签1,2昄��为字�W�S[1]S[2] = ab�?br>

Figure 9 After the insertion of the suffix abbabbaabbabb#

tree(3)�q�没完成�Q�因��没有��定新加的分支节点的后缀指针。这个分支节点的最长后�~�是b�Q�但是对应b的分支节点不存在。别惊慌�Q�下一个要创徏的分支节点就是对应b的节炏V�?br>
下一个要插入的后�~�是suffix(4)。这是刚插入的suffix(3)的最长后�~�。新后缀的插入过�E�由�Ҏ��当前�z�d��节点的后�~�指针��定新的�z�d��节点开始。由于根�l�点没有后缀指针�Q�活动节�Ҏ��有变化。因此activeLength也没有变化。但是，我们必须更新minDistance以满��lastBranchIndex(4,4) >= 4 + activeLength + minDistance。显�Ӟ��对于所有的i<= lastBranchIndex(i+1,i+1)。因此，lastBranchIndex(i+1,i+1) >= lastBranchIndex(i,i) >= i + activeLength + minDistance。�ؓ了保证lastBranchIndex(i+1,i+1) >= i + 1 + activeLength + minDistance�Q�我们必��d��minDistance减小1.

因�ؓminDistance = 1�Q�我们从�z�d��节点开始，沿着S[4]S[5]...指定的�\径记录。我们不需要比较开始的minDistance个字�W�，因�ؓ在minDistance+1之前的字�W�都已经保证是匹配的了。由于活动节点以S[4]=b开始的边的长度大于1,我们比较S[5]和边的第二个字符S[3]。因��两个字符不同�Q�这条边也要一分�ؓ二。第一条边的标�{��ؓ2,2=b�Q�第二条��的标签�?+。在两条边之间添加新的分支节点F�Q�还要�ؓ新插入的后缀创徏信息节点G。G跟F之间通过标签�?+的边�q�接。结果如图所�C��?br>

Figure 10 After the insertion of the suffix bbabbaabbabb#

现在我们要�ؓ插入后缀suffix(3)时创建的分支节点D讄��后缀指针。这个后�~�指针��是新创建的分支节点F�?br>
节点F表示的字�W�串b的最长后�~�是空丌Ӏ�因此F的后�~�指针指向根结炏V��图11是添加了后缀指针的结果�?br>

Figure 11 Trie of Figure 10 with suffix pointers added

下一个要插入的是suffix(5)。由于suffix(5)是刚插入的后�~�suffix(4)的最长后�~��Q�我们从�z�d��节点的后�~�指针开始。但是当前作为活动节点的根结�Ҏ��有后�~�指针。因此，�z�d��节点不变。�ؓ了保持lastBranchIndex, activeLength, minDistance以及��插入的后缀的烦�?5)之间的关�p�，需要将minDistance减少1.因此�Q�minDistance变�ؓ0.

因�ؓactiveLength=0�Q�我们需要从suffix(5)的首字符S[5]开始检查。活动节�Ҏ��一条以S[5]=b开始的辏V��我们沿着�q�条�Ҏ��较后�~�字符和标�{�֭��W�。由于所有的字符都匹配，我们到达节点F。现在F成�ؓ�z�d��节点�Q�在��查后�~�字符的过�E�中�Q�遇到的分支节点都成为新的活动节点）�Q�activeLength=1。我们从当前�z�d��节点的某条边开始��l�比较。由于下一个要比较的后�~�字符是S[6]=a�Q�我们��用以a开始的边（如果�q�样的边不存在，新后�~�的lastBranchIndex是activeLength+1�Q�。这条边的标�{�是3+。当比较到新后缀的字�W�S[10]=a和边的字�W�S[7]=b�Ӟ��比较�l�束。因此，lastBranchIndex(5,5) = 10. minDistance讄��为允许的最大��|��也就是lastBranchIndex(5,5) - (index of suffix to be inserted) - activeLength = 10 - 5 - 1 = 4.�?br>
��Z��插入suffix(5)�Q�我们将节点F和C之间的边分裂��Z��。分裂出现在�?F,C)的splitDigit=5的字�W�位�|��?br>

Figure 12 After the insertion of the suffix babbaabbabb#

后面几个后缀的插入过�E�跟前面几个完全一��P��׃��译了，感兴��的可以看看原文�Q�我只把图脓在这儿，如果上面的部分看明白了，那么只看下面的几张图也能明白是怎么插入的�?/font>

Figure 13 After the insertion of the suffix abbaabbabb#

Figure 14 After the insertion of the suffix bbaabbabb#

Figure 15 After the insertion of the suffix baabbabb#

Figure 16 After the insertion of the suffix aabbabb#

Figure 17 After the insertion of the suffix abbabb#

Figure 18 After the insertion of the suffix bbabb#

Figure 19 After the insertion of the suffix babb#

Figure 20 After the insertion of the suffix abb#

Figure 21 After the insertion of the suffix bb#

复杂度分�?/big>
用r表示字符串S的字�W�集的大��，n表示S的长度（也就是后�~�的数目）�?/n�Q�lastbranchindex(i,i)>
��Z��插入suffix(i)�Q�我�?/n�Q�lastbranchindex(i,i)>
(a)沿着�z�d��节点的后�~�指针�Q�除非活动节�Ҏ��根结点）�?/n�Q�lastbranchindex(i,i)>
(b)在已创徏的后�~�树中向下�U�d��Q�直到经�q�了minDistance个字�W��?/n�Q�lastbranchindex(i,i)>
(c)然后依次比较后缀和边的字�W�，直到��定了lastBranchIndex(i,i)为止�?/n�Q�lastbranchindex(i,i)>
(d)最后插入新的信息节点和可能的分支节炏V�?/n�Q�lastbranchindex(i,i)>

(a)部分消耗的�ȝ��旉��是O(n)�Q�一共有n此插入）

(b) 部分中，在后�~�树中往下移动时�Q�不需要做比较。每�ơ移动到下��分支节点需要O(1)旉��。另外，每次�U�d��都会使minDistance减少1.�׃��开始时 minDistance�?,�q�且永远不会��于0,(b)消耗的旉��是O(n + n�ơ插入操作中minDistance增加的��L��).

(c) 部分中，��定lastBranchIndex(i,i) �?i + activeLength + minDistance是否相等需要的旉��是O(1)。这只有在minDistance = 0或者位于suffix(i)的activeLength + minDistance + 1位置的字�W�x跟活动节点的合适的边的minDistance + 1位置的字�W�不同的时候才满��。当lastBranchIndex(i,i) != i + activeLength + minDistance�Ӟ��lastBranchIndex(i,i) > i + activeLength + minDistance�Q�lastBranchIndex(i,i)的值通过对后�~�字符和边的字�W�之间做一�p�d��的比较来��定。每�q�行一�ơ这�U�比较，minDistance�?.本算法中�Q�只有在�q�种情景下，minDistance才会增加。由于minDistance的每�ơ递增都是S的新的位�|? �Q�也��是此位�|�开始的字符�q�未比较�q�的位置�Q�的字符和边的字�W�相�{�的情�Ş的结果，因此在n�ơ插入中�Q�minDistance增加的��L��是O(n)�?/n�Q�lastbranchindex(i,i)>

每次插入�Ӟ��(d)消耗的旉��是O(r)�Q�因为我们需要初始化要创建的分支节点的O(r)个字�D�c��因此步�?d)消耗的�ȝ��旉��是O(nr)�?/n�Q�lastbranchindex(i,i)>

因此�Q�创建后�~�树消耗的�ȝ��旉��是O(nr)。如果假定字�W�集的大��r是常敎ͼ��法的复杂度��是O(n)�?/n�Q�lastbranchindex(i,i)>

只有在字�W�集的大��r很小的情况下�Q�才推荐每个分支节点有r个指向子节点的字�D�c��当字符集很大的时候（可能会跟n一样大�Q�这时上�q�算法的复杂度是O(n^2)�Q�，使用哈希�?/a>能够得到O(n)复杂度的��法。空间复杂度有O(nr)变�ؓO(n)�?/n�Q�lastbranchindex(i,i)>

�q�里有一个分�ȝ��法实现的后缀树，旉��和空间复杂度都是O(n)�Q�即使字�W�集的大��是O(n)�Q��?/n�Q�lastbranchindex(i,i)>

References and Selected Readings

Department of Energy's Web site for the human genomics project

Biocomputing Hypertext Coursebook.

Linear time algorithms to search for a single pattern in a given string can be found in most algorithm's texts. See, for example, the texts:

Computer Algorithms, by E. Horowitz, S. Sahni, and S. Rajasekeran, Computer Science Press, New York, 1998.

Introduction to Algorithms, by T. Cormen, C. Leiserson, and R. Rivest, McGraw-Hill Book Company, New York, 1992.

For more on suffix tree construction, see the papers:

``A space economical suffix tree construction algorithm,'' by E. McCreight, Journal of the ACM, 23, 2, 1976, 262-272.

``On-line construction of suffix trees,'' by E. Ukkonen, Algorithmica, 14, 3, 1995, 249-260.

Fast string searching with suffix trees,'' by M. Nelson, Dr. Dobb's Journal, August 1996.

Optimal suffix tree construction with large alphabets, by M. Farach, IEEE Symposium on the Foundations of Computer Science, 1997.

You can download C++ code to construct a suffix tree from http://www.ddj.com/ftp/1996/1996.08/suffix.zip. This code, developed by M. Nelson, is described in paper 3 above.

季阳 2008-07-12 10:44 发表评论

C++�~�码风格指南

季阳 — Fri, 23 May 2008 01:09:00 GMT

C++�~�码风格指南

C++ Programming Style Guidelines

季阳 2008-05-23 09:09 发表评论

ecb symboldef VS. si context window

季阳 — Mon, 21 Apr 2008 05:02:00 GMT
ZoundryDocument
一直觉得source insight中显�C�变量和函数定义的context window很好,昨天�H�然发现原来ecb(Emacs Code Browser)中也有个�c�M��的东�?当layout换成left_symboldef�?左下�H�口��是�?啥也不说�?贴个囑֐�.

�q�个是我�Ҏ��原先的layout left_symboldef改的.可以看到左边那一�?上面是函数啥的列�?下面��是�W�号定义�H�口.有两点不爽的是符号定义窗口没法单独放在下�?主要是放在左边的�?函数原型比较长的��没法完整显�C?二是不能像si那样双击跌��{.不过也不错了,跌��{用cscope也容�?

ps:我的ecb函数列表中没法显�C�参数类�?哪位如果知道�ȝ��说一下哈,谢了!

季阳 2008-04-21 13:02 发表评论

关于��和�~�冲区的理解

季阳 — Mon, 07 Apr 2008 04:48:00 GMT

0. 序曲

写这��短文的起因�?前两天想��d��大的acm在线�pȝ��扑և�道题做做。�ؓ什么呢?因�ؓ本�h天大毕业,�q�个天大呢可是中国最早的大学,原名北洋大学�?�q�可�l�对是货真�h实的�W�一所大学。给大家推荐推荐�?学风那是相当的好�?/p>
扯多�?�q�是回到本来的话题上。上了acm�pȝ��之后,��先看了1001。那道题的意思是输入一些正整数(以EOF�l�束),把对应的字符输出。这个简�?�E�序很快��出来了:

#include <stdio.h>
int main()
{
int c;
while(scanf("%d", &c) != EOF)
{
putchar(c);
}
return 0;
}

�E�序�q�行,输入103 102 105 107

输出gfik�?/p>
当时�q�行完之后马上想,��Z��么不是输入一个数字马上输��Z��个字�W�呢,因�ؓ看程序确实是�q�样的逻辑,只要不是EOF,��׃��输出。又一�?对了,是缓冲的问题。想��h��APUE里边说得stdin应该是行�~�冲�?另外,可以用setbuf,setvbuf讑֮��的�~�冲。于是想��stdin设成无缓冲的。于是程序变成这�?

#include <stdio.h>
int main()
{
int c;
setbuf(stdin, NULL);
while(scanf("%d", &c) != EOF)
{
putchar(c);
}
return 0;
}

可是�~�译�q�行,�q�是老样�?没有变化。想了想,没想出是啥原�?于是开始google和APUE。终于算是明白了�?整理在这�ѝ�?/p>

声明�Q?/p>

本文很大部分内容来自APUE�Q�－UNIX环境高��~�程�?/p>

1. �~�冲�c�d��?/p>
标准库提供缓冲是��Z��减少对read和write的调用。提供的�~�冲有三�U�类�?整理自APUE):

全缓册Ӏ?

在这�U�情况下,实际的I/O操作只有在缓冲区被填满了之后才会�q�行。对�ȝ��在磁盘上的文件的操作一般是有标准I/O库提供全�~�冲。缓冲区一般是在第一�ơ对��进行I/O操作�?由标准I/O函数调用malloc函数分配得到的�?/p>
术语flush描述了标准I/O�~�冲的写操作。缓冲区可以由标准I/O函数自动flush(例如�~�冲区满的时�?;或者我们对��调用fflush函数�?/p>

行缓�?/div>

在这�U�情况下,只有在输�?输出中遇到换行符的时�?才会执行实际的I/O操作。这允许我们一�ơ写一个字�W?但是只有在写完一行之后才做I/O操作。一般的,涉及到终端的��?-例如标注输入(stdin)和标准输�?stdout)--是行�~�冲的�?/p>

无缓�?/div>

标准I/O库不�~�存字符�?span style="color: #ff0000;">需要注意的�?标准库不�~�存�q�不意味着操作�pȝ��或者设备驱动不�~�存�?br>

ISO C要求:

当且仅当不涉及交互设备时,标准输入和标准输出是全缓存的�?/span>

标准错误�l�对不是全缓存的�?/span>

但是,�q��ƈ没有告诉我们当标准输�?输出在涉及交互设备时,它们是无�~�存的还是行�~�存�?也没有告诉我们标准错误应该是行缓存的�q�是无缓存的。不�q?大多数实现默认的�~�存�c�d��是这��L��:

标准错误��L��无缓存的�?/span>

对于所有的其他��来�?如果它们涉及��C��互设�?那么��是行缓存的;否则是全�~�存的�?/span>

2. 改变默认�~�存�c�d��

可以通过下面的函数改变缓存类�?摘自APUE):

void setbuf(FILE *restrict fp, char *restrict buf);
int setvbuf(FILE *restrict fp, char *restrict buf, int mode, size_t size);

�q�些函数必须在流打开之后、但是未�Ҏ��做�Q何操作之前被调用(因�ؓ每个函数都需要一个有效的文�g指针作�ؓ�W�一个参�?�?/span>

利用setbuf�Q�可以打开或者关闭缓存。�ؓ了打开�~�存�Q�buf参数必须一个大��ؓBUFSIZ的缓存，BUFSIZ是定义在stdio。h中的帔R��?amp;amp;lt;<ISO/IEC 9899>>要求�Q�BUFSIZ臛_��?56。如果要关闭�~�存�Q�可以将buf设成NULL�?/span>

利用setvbuf�Q�我们可以设定缓存类型。这是通过mode参数指定的�?/span>

关于�q�两个函敎ͼ�可以看下表（摘自APUE�Q�：

Function

mode

buf

Buffer and length

Type of buffering

setbuf

non-null

user buf of length BUFSIZ

fully buffered or line buffered

NULL

(no buffer)

unbuffered

setvbuf

_IOLBF

non-null

user buf of length size

fully buffered

NULL

system buffer of appropriate length

_IOFBF

non-null

user buf of length size

line buffered

NULL

system buffer of appropriate length

_IONBF

(ignored)

(no buffer)

unbuffered

需要注意的是：如果在函数内为流分配了自动变量作为缓存，那么在退��Z��前需要将��关闭。因此最好让�pȝ��自己分配�~�存�Q�这些缓存在��关闭的时候会自动被释放�?/span>

3.如果清理输入�~�存

关于�q�点可以参看comp.lang.c FAQ的Question12.26b:

Q: If fflush won't work, what can I use to flush input?

A: It depends on what you're trying to do. If you're trying to get rid of an unread newline or other unexpected input after calling scanf (see questions 12.18a-12.19), you really need to rewrite or replace the call to scanf (see question 12.20). Alternatively, you can consume the rest of a partially-read line with a simple code fragment like

while((c = getchar()) != '\n' && c != EOF)
/* discard */ ;

(You may also be able to use the curses flushinp function.)

There is no standard way to discard unread characters from a stdio input stream. Some vendors do implement fflush so that fflush(stdin) discards unread characters, although portable programs cannot depend on this. (Some versions of the stdio library implement fpurge or fabort calls which do the same thing, but these aren't standard, either.) Note, too, that flushing stdio input buffers is not necessarily sufficient: unread characters can also accumulate in other, OS-level input buffers. If you're trying to actively discard input (perhaps in anticipation of issuing an unexpected prompt to confirm a destructive action, for which an accidentally-typed ``y'' could be disastrous), you'll have to use a system-specific technique to detect the presence of typed-ahead input; see questions 19.1 and 19.2. Keep in mind that users can become frustrated if you discard input that happened to be typed too quickly.

References: ISO Sec. 7.9.5.2
H&S Sec. 15.2

4. 几点需要注意的地方

对输入流�q�行fflush操作是无定义的�?/span>

无缓存�ƈ不意味着一个个的那样处理输入，而是说当操作�pȝ��q�回它们�Ӟ��对于标准库函数来说它们是立即可用的。因��可能有操作系�l��甚至是硬件��的缓存，�q�些�q�不是setbuf可以控制的�?/span>

另外可以参�?a >�q�里�Q�我��是最先从�q�里开始看的）。还�?a >�q�里。我从后面那个链接摘录一些重要的下来�Q?/span>

setbuf() has to do with the delivery of bytes between the
C library FILE* management layer and the OS I/O layer.

Calls to fread(), fgets(), fgetc(), and getchar() work within
whatever FILE* buffered data is available, and when that data
is exhausted, the calls request that the FILE* buffer be refilled
by the system I/O layer.

When full buffering is turned on, that refill operation results in the
FILE* layer requesting that the operating system hand it a full
buffer's worth of data; when buffering is turned off, that
refill operation results in the FILE* layer requesting that the
operating system return a single character.

...setting an input stream to be unbuffered
does NOT tell the operating system to tell the device driver
to go into any kind of "raw" single-character mode. There are
system-specific calls such as ioctl() and tcsetterm() that
control what the device driver will do.

季阳 2008-04-07 12:48 发表评论

makefile�W�记

季阳 — Sun, 24 Feb 2008 03:23:00 GMT
    注：�q�里的makefile指的是gnu makefile�Q�可能跟其他的makefile略有不同。若有不同，我尽量提及。而且�q�也不算是一��教�E�，只是我在用make的时候记得一些笔记。推荐看<>。另外网上有一��《跟我一起写makefile》也很好�?br />
    makefile规则分�ؓ三部分：目标(target)、条�?prerequisite)、命�?commands)�?br />    target:prereq1...prereqn
       commans

1.自动变量

    $@�Q�代表目标文件名
    $%�Q�The filename element of an archive member specification.
    $<�Q�条件列表中的第一个条件的文�g�?br />    $?�Q�条件列表中所有比目标新的那些条�g的文件名�Q�以�I�格分割
    $^�Q�条件列表中所有条件的文�g名，以空格分剌Ӏ�如果列表中有重复的条�g�Q�则会被删掉�?br />    $+�Q�跟$^�c�M��Q�区别在不会��L��重复的条件�?br />    $*�Q�目标文件名的词�q�部�?��L��扩展名剩下的部分)

    自动变量只能用在规则的命令部分，因�ؓ�q�些变量是make匚w��到规则的目标和条件后才设�|�值的�?br />    举个例子说明一下。假设某个工�E�有三个文�g�Q�cal.cpp�Q�cal.h�Q�test.cpp(下面再有说明时也以此��Z��)。makefile如下�Q?br />        OBJS=test.o cal.o cal.o

        TARGET=cal.exe

        all:$(TARGET)

    $(TARGET):$(OBJS)
            @echo $@
        @echo $<
        @echo $^
        @echo $?
        @echo $+
        @echo $%
        @echo $*
    输出为：
            cal.exe
            test.o
            test.o cal.o
            test.o cal.o
            test.o cal.o cal.o
            ECHO is off.
            ECHO is off.
    至于最后两个�ؓ什么会�q�样输出我还不太清楚�Q�有清楚地麻烦告诉我一下这两个怎么用。先谢谢�?/b>�?br />
2.模式规则
    模式规则也是规则�Q�也要满��make的规则�Ş式，分�ؓ目标、条件、命令三个部分。只是目标、条件中的文件名的词�q�部分用%代替了，�q�个%跟shell中的*�c�M��Q�代表�Q意长度的字符丌Ӏ�还以上面说得工�E��ؓ例，makefile如下�Q?br />        CPPFLAGS= -g
        CC=g++

        test:cal.o test.o
        cal.o:cal.h
    make的时候，输出如下内容�Q?br />        g++ -g -c -o test.o test.cpp
        g++ -g -c -o cal.o cal.cpp
        g++   test.o cal.o   -o test
    �q�个makefile之所以能够正��被处理�Q�是因�ؓmake内徏了一些规则。例如：
        %.o: %.c
            $(COMPILE.c) $(OUTPUT_OPTION) $<
        %.o: %.cpp
            $(COMPILE.cpp) $(OUTPUT_OPTION) $<
    以及
        %: %.o
            $(LINK.o) $^ $(LOADLIBES) $(LDLIBS) -o $@
    �q�些规则里面�?变量都是make的标准变�?�q�有上面的CPPFLAGS,CC也是。另外还有一些别�?�Q�这些标准变量有的有默认�?例如CC的默认值是cc)�Q�有的没有。make在处理makefile文�g�Ӟ��如果没有昑ּ�的规则，那么��׃��查找是否有隐式的可用规则�Q�如果找到就会利用隐式规则来生成目标�?br />
    2.1静态模式规�?br />       静态模式规则指的是�c�M��下面的规则：
        $(OBJECTS): %.o: %c
            $(CC) -c $(CFLAGS) $< -o $@
       �q�跟上面的模式规则类��|��不同在于��规则的适用范围限制在了$(OBJECTS)。也��是只针对这些目标来应用规则�?br />
    2.2后缀规则
       后缀规则是指用一个或者两个后�~��q�接��h��作�ؓ目标�Q�同时省略掉条�g部分。如下：
       .c.o:
           $(COMPILE.c) $(OUTPUT_OPTION) $<
       �Ҏ��h��的地�Ҏ��条�g后缀在前�Q�目标后�~�在后�?br />       �q�跟上面的规则：
           %.o: %.c
               $(COMPILE.c) $(OUTPUT_OPTION) $<
       功能是一��L��Q�只是�ؓ了兼容一些老的make�pȝ��?br />       需要注意的是，�q�里用到的后�~�必须在已知后�~�列表里面。有个专用的目标(target)—�?SUFFIXES——用来设定后�~�列表。例如：.SUFFIXES�Q?pdf .o .c 。�?SUFFIXES:�Q�也��是后面列表为空�Q�用来清�I�后�~�列表�?br />

3.自动依赖生成
    �q�没发现�q�个在实际应用中有多方便�Q�有兴趣的可以看看我开始推荐的两个文档�?br />

季阳 2008-02-24 11:23 发表评论

�l�于体会到emacs比vim方便的地方！

季阳 — Sat, 16 Feb 2008 15:48:00 GMT

    刚刚试用了一下在emacs里用gdb调试�E�序�Q�不是一般的方便啊，呵呵。有直观的界面，而且�q�有console对gdb方便的控�Ӟ��使用了好几天emacs了，觉得�q�是��有的比vim方便的地斏V�?/p>
    当然�Q�单�U�用来编辑文件的话还是vim方便一些，毕竟vim区分模式�Q�有些操作可以用很少的按键快速的完成�?/p>
    不知道emacs的宏录制功能如何。感觉vim里面的宏真的是太好用了，弄得我很是舍不得vim。要是有个编辑器能集合vim的高效快捯��emacs的强大扩展能力就好了�?/p>

季阳 2008-02-16 23:48 发表评论

Blog api

季阳 — Sat, 16 Feb 2008 15:39:00 GMT

cpp blog api

http://www.shnenglu.com/lucency/services/metaweblog.aspx

google blog api

http://www.blogger.com:80/feeds/default/blogs

季阳 2008-02-16 23:39 发表评论

Function	mode	buf	Buffer and length	Type of buffering
`setbuf`		non-null	user buf of length `BUFSIZ`	fully buffered or line buffered
`setbuf`		`NULL`	(no buffer)	unbuffered
`setvbuf`	`_IOLBF`	non-null	user buf of length size	fully buffered
	`_IOLBF`	`NULL`	system buffer of appropriate length	fully buffered
	`_IOFBF`	non-null	user buf of length size	line buffered
	`_IOFBF`	`NULL`	system buffer of appropriate length	line buffered
	`_IONBF`	(ignored)	(no buffer)	unbuffered

久久av无码专区亚洲av桃花岛,久久精品国产一区二区三区日韩,久久久久AV综合网成人

All about Awk[译]

gdb基础

gdb

一.概述

�?gdb命��o

命��o语法

命��o补全

获取帮助

�?�C�Z��1

断点

删除断点

���用断点

断点条�g

指定位置

�?/h3> 待添�?/p>

数据

�?�C�Z��2

�?后记

Suffix Trees[译]

C++�~�码风格指南

ecb symboldef VS. si context window

关于���和�~�冲区的理解

makefile�W�记

�l�于体会到emacs比vim方便的地方！

Blog api

��用断点

�?/h3>
待添�?/p>

关于��和�~�冲区的理解