归有光&&阅读：7420次&&
原文项脊轩，旧南阁子也。室仅方丈，可容一人居。百年老屋，尘泥渗（shèn）漉（lù），雨泽下注；每移案，顾视无可置者。又北向，不能得日，日过午已昏。余稍为修葺（qì），使不上漏。前辟四窗，垣墙周庭，以当南日，日影反照，室始洞然。又杂植兰桂竹木于庭，旧时栏J（shǔn），亦遂增胜。借书满架，偃仰啸歌，冥然兀坐，万籁有声；而庭阶寂寂，小鸟时来啄食，人至不去。三五之夜，明月半墙，桂影斑驳，风移影动，珊珊可爱。然余居于此，多可喜，亦多可悲。先是,庭中通南北为一。迨（dài）诸父异爨（cuàn），内外多置小门，墙往往而是。东犬西吠，客逾庖（páo）而宴，鸡栖于厅。庭中始为篱，已为墙，凡再变矣。家有老妪（yù）， 尝居于此。妪，先大母婢也，乳二世，先妣（bǐ）抚之甚厚。室西连于中闺，先妣尝一至。妪每谓余曰：“某所，而母立于兹。”妪又曰：“汝姊（zǐ）在吾怀，呱呱（gū）而泣；娘以指叩门扉曰：‘儿寒乎？欲食乎？’吾从板外相为应答。”语未毕， 余泣，妪亦泣。余自束发读书轩中，一日，大母过余曰：“吾儿，久不见若影，何竟日默默在此，大类女郎也？”比去，以手阖门，自语曰：“吾家读书久不效，儿之成，则可待乎！”顷之，持一象笏（hù）至，曰：“此吾祖太常公宣德间执此以朝，他日汝当用之！”瞻顾遗迹，如在昨日，令人长号不自禁。轩东故尝为厨，人往，从轩前过。余扃（jiōng）牖（yǒu）而居，久之，能以足音辨人。轩凡四遭火，得不焚，殆有神护者。项脊生曰：“蜀清守丹穴，利甲天下，其后秦皇帝筑女怀清台；刘玄德与曹操争天下，诸葛孔明起陇中。方二人之昧昧于一隅也，世何足以知之，余区区处败屋中，方扬眉、瞬目，谓有奇景。人知之者，其谓与坎井之蛙何异？”余既为此志，后五年，吾妻来归，时至轩中，从余问古事，或凭几学书。 吾妻归宁，述诸小妹语曰：“闻姊家有阁子，且何谓阁子也？”其后六年，吾妻死，室坏不修。其后二年，余久卧病无聊，乃使人复葺南阁子，其制稍异于前。然自后余多在外，不常居。庭有枇杷树，吾妻死之年所手植也，今已亭亭如盖矣。字词注释1、轩：窗，引申为有窗的小室。2、旧：旧日的，原来的。3、方丈：一丈见方。4、尘泥渗漉 ：从小孔慢慢漏下。渗，透过。漉，漏下。5、雨泽下注：下，往下。 雨泽：雨水。6、案：几案，桌子。7、顾视：环看四周。8、不能得日：得日，照到阳光。9、日过午已昏：昏，光线不明。10、修葺：修缮、修理。11、辟：开。12、垣墙周庭：庭院四周砌上围墙。垣，矮墙，也泛指墙。周庭，把院子四周围住。13、当：抵挡。14、洞然：透明敞亮。15、栏J：栏杆。16、增胜：增添了光彩。17、偃仰：俯仰，这里指安居，休息，形容生活悠然自得。偃，仰卧。18、啸歌：长吟或吟唱。这里指吟咏诗文，显示豪放自若。啸，口里发出长而清越的声音。19、冥然兀坐：静静地独自端坐着。兀坐，端坐。20、万籁有声：一切声音都能听到。万籁，指自然界的一切声响。籁，孔穴里发出的声音，也指一般的声响。21、三五之夜：农历每月十五的夜晚。22、珊珊：形容衣裾玉佩的声音，引申为美好的样子。23、束发：古代男孩成童时束发为髻，束发指儿童时代。24、迨(dài)诸父异爨（cuàn）：等到伯、叔们分了家。迨，及，等到。诸父，伯父、叔父的统称。异爨，分灶做饭，意思是分了家。25、往往：指到处，处处。26、东犬西吠：东家的狗对着西家的狗叫。意思是分家后，狗把原住同一庭院的人当作陌生人。27、逾庖而宴：越过厨房而去吃饭。庖，厨房28、已：已而，随后不久。29、凡再变矣：凡，总共。再，两次。30、竟日：一天到晚。竟，从头到尾。31、相为应答：对她作出回答。32、阖（hé）：关闭。33、扃(jiōng)牖(yǒu)：扃，关闭。牖，窗户。34、瞻顾遗迹：回忆旧日事物。瞻顾，泛指看，有瞻仰、回忆的意思。35、殆：大概，表示揣测的语气。修葺：修缮，修理。36、来归：嫁到我家来。归，女子出嫁。37、凭几学术：伏在几上学写字。几，小或矮的桌子。38、归宁：出嫁的女儿回娘家省亲。39、制：指建造的格式和样子。40、手植：亲手种植。41、亭亭如盖：高高挺立，树冠像车盖一样。42、制：规制，格局。43、老妪：老年妇女44、先大母：已故的祖母。大母：祖母45 、先妣：已故的母亲46，中闺：指内室47. 阁子:小的房室翻译项脊轩，是过去的南阁楼。屋里仅仅一丈见方，只可容纳一个人居住。这是已有上百年的老屋子，(屋顶墙上的)泥土从上边漏下来，雨水也往下流；每当移动书桌时，左看右看没有可以安放的地方。又朝北，不能照到阳光，天一过中午就已经昏暗。我稍稍修理了一下，使它不从上面漏土漏雨。前面开了四扇窗子，院子四周砌 上围墙，用来挡住南面射来的日光，日光反照，室内才明亮起来。又在庭院里错杂地种上兰花、桂树、竹子等，往日的栏杆，也就增加了新的光彩。书籍摆满了书架，我安居室内，吟诵诗文，有时又静静地独自端坐，听到自然界各种各样的声音；庭院、阶前却静悄悄的，小鸟不时飞下来啄食,人到它前面去也不离开。十五的夜晚，明月高悬，照亮半截墙壁，桂树的影子交杂错落，微风吹来，花影摇动，很是可爱。然而我住在这里，有许多值得高兴的事，也有许多值得悲伤的事。 在这以前，庭院南北相通成为一体。等到伯父叔父们分了家，在室内外设置了许多小门和墙壁，到处都是。东家的狗对着西家叫，客人得越过厨房去吃饭，鸡在厅堂里栖息。庭院中开始是篱笆隔开，然后又砌成了墙，一共变了两次。家中有个老婆婆，曾经在这里居住过。这个老婆婆，是我死去的祖母的婢女，给两代人喂过奶，先母 对她很好。房子的西边和内室相连，先母曾经常常来。老婆婆常常对我说：“这个地方，你母亲曾经站在这儿。”老婆婆又说：“你姐姐在我怀中，呱呱地哭泣； 你母亲用手指敲着房门说：‘孩子是冷呢?还是想吃东西呢?’我隔着门一一回答。”话还没有说完，我就哭起来，老婆婆也流下了眼泪。我从十五岁起就在轩内读书，有一天，祖母来看我，说：“我的孩子，好久没有见到你的身影了，为什么整天默默地呆在这里，真像个女孩子呀?”等到离开时，用手关上门，自言自语地说：“我们家读书长久没有得到功效，这孩子长大，就可以有指望了呀!”不一会，拿着一个象笏过来，说：“这是我祖父太常公宣德年间拿着去朝见皇帝用的，以后你会用到它!”回忆起旧日这些事情，就好像发生在昨天一样，真让人忍不住放声大哭。项脊轩的东边曾经是厨房，人们到那里去，必须从轩前经过。我关着窗子住在里面，时间长了，能够根据脚步声辨别是谁。项脊轩一共遭过四次火灾，能够不被焚毁，大概是有神灵在保护着吧。我说：“蜀国的寡妇清继承并守住了朱砂矿，利润天下第一。后来秦朝皇帝为她建造了怀青台。刘备与曹操争夺天下，诸葛亮从隆中起家，当诸葛亮和清在角落不被人知道的时候，世人怎么能够知道他们两？我渺小地在项脊轩，正扬起眉毛眼睛一睁一闭，以为会有奇特的景象，知道这种情况的人认为我和浅井的青蛙有什么区别。我已经作了这篇志，过了五年，我的妻子嫁到我家来，她时常来到轩中，向我问一些旧时的事情，有时伏在桌旁学写字。我妻子回娘家探亲，回来转述她的小妹妹们的话说：“听说姐姐家有个小阁楼，那么，什么叫阁子呢?”这以后六年，我的妻子去世，项脊轩破败没有整修。又过了两年，我很长时间生病卧床无事可干，就派人再次 修缮南阁子，格局跟过去稍有不同。然而此后我多在外边，不常住在这里。庭院中有一株枇杷树，是我妻子去世那年亲手种植的，现在已经高高挺立，枝叶繁茂像伞一样了。古今异义1.项脊轩，旧南阁子也 （旧，原来的）2.南北为一 （一，整体）3.室仅方丈 （方丈，一丈见方）4.往往而是（往往，到处）5.凡再变矣 （凡，总共；再，两次）6.每移案，顾视无可置者 （案，桌子）7.久不见若影 （若，你）8.日过午已昏 （昏，暗）9.或凭几学书（几，书桌；书，写字）10.杂植兰桂竹木于庭 （杂，交错）11.比去，以手阖门（比，等到）12.亦遂增胜 （胜，佳景，引申为光彩）13.吾妻来归 （归，旧时指女子出嫁）14.始为篱，已为墙 （已，后来、不久）15.三五之夜 （三五，即农历十五）16.何竟日默默在此，大类女郎也 （竟，整）17.且何谓阁子也 （且，那么）18.余稍为修葺 （余，我）19.雨泽下注 （下注，向下流）20.先大母婢也，乳二世（乳，喂养）21.余自束发 （束发，表示成童）一词多义1.始室始洞然 （才，方才，副词）庭中始为篱，已为墙 （起初、先，副词）2.过日过午已昏 （偏过，动词）大母过余曰 （访，探望，动词）从轩前过（经过动词）3.置顾视无可置者 （放置，动词）内外多置小门 （设置，动词）4.而余扃牖而居 （助词，表修饰，无义）万籁有声，而庭阶寂寂 （但，表转折，连词）墙往往而是 （连接状语和中心词，相当于“地”，也可不译，连词）某所，而母立于兹 （通“尔”，你，你的，代词）5.为始为篱，已为墙 （是，扎，动词）轩东故尝为厨 （是，动词）庭中通南北为一 （是，成为，动词）吾从板外相为应答 （作，介词）6.以以当南日 （用来，介词，表目的）能以足音辨人 （凭借、根据，介词）执此以朝 （用如“而”，介词）7.谓且何谓阁子也 （叫作，动词）妪每谓余曰 （告诉，动词）8.一庭中通南北为一 （整体，名词）先妣尝一至 （常来，副词）9.日不能得日 （阳光，名词）日过午已昏 （太阳，名词）一日，大母过余曰 （天，一昼夜，名词）10.先先是，庭中通南北为一 （以前，名词）先大母婢也 （去世的，形容词）11.前前辟四窗 （名词作状语，在前方，行为方向）从轩前过 （前面，形容词）12.之吾妻死之年所手植也（助词，的）他日汝当用之 （代象笏，代词）儿之成 （主谓间取消句子独立性）13.西东犬西吠 （向西边，副词）室西连于中闺 （……的西边，形容词）14.得不能得日 （得到，获得，动词）得不焚 （能，能够，助动词）15.已日过午已昏 （已经，副词）已为墙 （然后，副词）16.当以当南日 （挡住，动词）他日汝当用之 （应当，应该，助动词）17.然室始洞然 （……的样子，词尾）然余居于此 （然而，但是，连词）18.书借书满架 （书，书籍，名词）或凭几学书 （写字，动词）19.食小鸟时来啄食 （食物，名词）欲食乎 （吃，动词）20.大先大母婢也 （大母，指祖母）大类女郎也 （很，非常，副词）21.所某所而母立于兹 （地方，处所，名词）吾妻死之年所手植也 （……的，在此指代枇杷树，特殊的指示代词）22.从吾从板外相为应答 （由，自，介词）从余问古事 （向……学习，动词）23.自余自束发 （从，由，介词）自语曰：“……” （自己，代词）24.归吾妻来归 （女子出嫁，动词）吾妻归宁 （归，返回，动词。归宁，出嫁的女儿回娘家探望）25.每每移案，顾视无可置者（每逢）妪每谓予曰：“某所，而母立于兹。”（常常）每字有二十余印（每个）通假字1.珊珊可爱（“珊珊”通“姗姗” ，美好的样子）2.以当南日（“当”通“挡” ）3 而母立于兹（“而”通“尔”）4 以手阖门（“阖”通“合”）词类活用1．名词用作动词（1）乳二世 （乳，抚养）（2）客逾庖而宴 （宴,赴宴）（3）执此以朝 （朝，上朝）（4）吾家读书久不效 （效，取得效果，此指考取功名）（5）或凭几学书 （书，写字）2．名词用作状语（1）雨泽下注。使不上漏（下，朝下，上，从上面）（2）前辟四窗 （前，指阁子北面，因阁子是向北的）（3）又北向 （北，朝北）（4）东犬西吠 （西，朝西，行为方向，指西家）（5）室西连于中闺（西，在西面）（6）吾妻死之年所手植也（手，亲自）（7）内外多置小门窗（在内外）（8）垣墙周庭（用垣墙）（9）时至轩中（不时）3．形容词用作名词多可喜，亦多可悲 （多，许多事）4. 数词用作名词庭中通南北为一 （一，一体，整体）句式1.判断句1) 此吾祖太常公宣德执此以朝，他日汝当用之2) 轩东故尝为厨用“……也”表示判断。如：3) 项脊轩，旧南阁子也4) 妪，先大母婢也2.省略句下列各句中的括号表示省略了的成分。如：1) （ ）又杂植兰桂竹木于庭 （省主语“余”）2) （ ）借书满架 （省主语“余”）3) 吾儿，（ ）久不见若影 （省主语“吾”）4) 使（ ）不上漏 （省兼语“之”）5) 明月（ ）半墙 （省谓语“照”）6) 余自束发读书（ ）轩中 （省介词“于”）7) 垣墙（ ）周庭 （省介词“于”）3.倒装句介词结构后置。下列各句状语（下划线）放在动词、形容词（粗体）之后。翻译时，一般将状语前移。如：1) 杂植兰桂竹木于庭 （在庭院里种兰桂竹木）2) 家有老妪，尝居于此 （在这里居住）3) 室西连于中闺 （与中闺相连）4) 鸡栖于厅 （在厅里栖息）5) 其制稍异于前 （跟以前不同）4.被动句1)得不焚 意念被动句5.宾语前置令人长号不自禁
1.王安石2.王羲之3.苏轼4.司马迁5.杜牧6.佚名7.归有光8.庄子9.荀况10.王勃11.屈原12.韩愈13.庄子14.贾谊15.李密16.陶渊明17.孟子18.左传僖公三十年19.苏辙20.司马迁
标签关键字：
文言文,文言文大全,文言文翻译,文言文阅读,注释,小学文言文,初中文言文,高中文言文,古文观止当前访客身份：游客 [
已有文章 2081 篇
当前位置：
Ukkonen 的后缀树算法的清晰解释
英文原文：
0人收藏此文章,
推荐于 2年前 (共 16 段, 翻译完成于 07-28) ()
参与翻译(2人)：
本文试图描述Ukkonen算法，首先显示当字符串是简单的(即不包含任何重复的字符)时候它做什么，然后扩展到完整的算法。
首先来看一些前言：
我们正在建设的，基本上像一个搜索特里结构（单词查找树）。所以有一个根节点，从根节点引出新的节点，以及进一步从新节点引出其它节点，依次类推。
但是：与搜索单词查找树中不同，边标签不是单个字符。相反,每个边的标签是使用一对整数[从哪,到哪]。这些都是指向文本的指针。从这个意义上说，每个边有任意长度的字符串标签，但只需要O(1)的空间(两个指针)。
&翻译的不错哦!
我想首先展示如何创建一个特别简单的字符串的后缀树，这个字符串没有重复的字符，如：
这个算法工作的步骤，从左到右。字符串的每个字符都有一个步骤。每一步都可能涉及到多个个体的操作,但是我们将会看到(见结尾最后的观察)的总数量操作是O(n)。
所以我们从左开始，第一次插入单个字符“a“创建一个从根节点(在左边)到一个叶节点的边，和作为[0,#)的标签，这意味着边代表了子串在位置0开始，结束在当前的结尾。我使用符号#来表示当前末尾，这是在位置1(a之后的右边)。
&翻译的不错哦!
因此，我们拥有一棵起始树，这棵树看起来如下：
而其意义如下：
现在我们前进到位置2(b的右边）。 我们每个步骤的目标是插入至当前位置的所有后缀。
我们通过以下动作完成目标：
&扩展已存在边a为ab
&插入一条新边b
在我们的图示里，它看起来如下：
而其意义如下：
我们看到了两点：
ab边的图示与它在起始树:[0,#]边的图示是相同的。它的意义却已经自动更改了，因为我们把当前的位置#从1更改到2。
每条边使用的空间复杂度为O(1),因为无论边代表多少个字符 ，它都是由指向文本里的两个指针组成。
接着我们再次增加位置，并且修改树：给每个已经存在的边增加c，插入一条表示新后缀c的边。
在我们的图示里，它看起来如下：
而其意义如下：
我们看到：
& 这棵树是经过上面的每个步骤后至当前位置的正确的后缀树。
& 步骤数目与文本中包含的字符一样多。
& 每个步骤的工作量是O(1)，因为所有已经存在的边都是增加#来自动更改的，而且为最后一个字符插入一条新边的时间复杂度为& O(1)。因此对一个长度为n的字符串来说，只需要O(n)时间复杂度。
&翻译的不错哦!
第一次扩展：简单的重复
当然，后缀树表示的如此良好只是因为我们的字符串没有包含任何重复。现在我们看一个更真实的字符串：
abcabxabcd 这个字符串像前面例子里一样是abc开始的，接着重复ab ，紧跟着x，再接着重复abc，紧跟着d。
步骤1到3：经过了前三个步骤后，我们拥有了前面例子的那棵树：
步骤4：我们移动#到位置4。这隐含地更改所有已经存在的边为如下：
而且我们需要在根节点插入当前步骤的最末的后缀a。
我们做这些之前，我们引入除#之外的
两个或者更多变量，当然这些变量一直都存在，只是我们迄今为止没有使用它们：
&& 活动点，它是一个三元组（活动节点，活动边，活动长度）
&& 剩余后缀数，它是一个整数，来说明我们需要插入多少个新的后缀。
&翻译的不错哦!
这两个图示的确切含义不久就会清晰，不过现在我们只能说：
&在简单的abc例子里，活动点总是(root,'0x',0),也就是说，活动节点是根节点，活动边是由空字符'0x'指定的边，活动长度是0。这么做的结果是我们在每一步骤里插入的一条新边是作为新创建的边插入到根节点。不久我们就会明白为什么需要三元组表示这条信息。
&在每个步骤开始时剩余后缀数总是设置为1。它的意义是我们主动插入到每一步骤末尾的后缀数目是1（总是最后一个字符）。
现在将有变化了，当我们给根节点插入当前最后一个字符a的时候，我们特别注意到已经存在一条以a开始的边：abca。在这种情况下我们做如下工作：
我们不向根节点插入一条新边[4,#]。相反，我们只是注意到后缀a已经在我们的树里。它终止在更长的边的中间位置，不过这么做我们并不疑惑，我们还是保留它们原来的样子。
我们设置活动点为(root,'a',1)。这意味着活动点现在是在根节点的以a开始的向外的边的中间某个位置，具体地指这条边的位置1之后。我们注意到这条边只是由它的首个字符a来声明的。这就足够了，因为以一个特定的字符开始的只有一条边（通读整个文档之后可以确定这是真的）。
我们还增加了剩余后缀数， 那么在下一步骤开始的时候，剩余后缀数为2。
&翻译的不错哦!
注意：当发现我们需要插入的最终后缀已经存在在这棵树里的时候，这棵树本身根本就没有改变（我们只是修改了活动节点和剩余后缀数）。那么这棵树就不再是能准确的表示至当前位置的后缀树了，不过它包含了所有的后缀（因为最终的后缀a隐含地包含了）。因此，除了修改变量外（所有这些变量都是定长的，因此空间复杂度是 O(1)），在这一步里没有做其他工作。
步骤5：我们修改当前的位置#为5。这将自动地如下更新这棵树：
由于剩余后缀数为2 ，我们需要插入目前位置的两个最终后缀：ab和b。这主要是因为：
前一步骤的a后缀从来都没有真正地插入。因此它保留下来，然而由于我们已经向前走了一步，它现在由a延长为ab。
&还有，我们需要插入新的最终边b。
&实际上，这意味着我们要修改活动点（它现在指向的是abcab边里的a之后），而且插入当前的最后一个字符b，
不过：同时它也证明b也 已经出现在同一条边里。
&因此，我们再次不修改这棵树，我们只是：
&修改活动点为(root,'a',2)(是与前面相同的节点和边，只不过现在我们指向到b之后)
&增加剩余后缀数为3 ，因为我们仍然不能插入前一个步骤的最终边，同时我们也不能插入当前的最终边
&翻译的不错哦!
为了清晰地说明：我们需要在当前的步骤里插入ab和b，不过由于ab已经找到，所以我们修改了活动点，而且甚至不试图插入b。为什么？因为如果ab处于这棵树里，那么它的每个后缀（包括b)也一定在这棵树里。也许仅仅是隐含性的，不过它一定在这棵树里，因为这是我们迄今为止建立这棵树所采用的方法。
我们增加#而前进到步骤6。这棵树自动修改为：
由于剩余后缀数是3 ，我们不得不增加abx,bx和x。活动点告诉我们ab结束在哪儿，因此我们仅仅需要跳过这儿，然后插入x。x确实还不在这棵树里，因此我们分割abcabx边，插入一个内部节点：
这条边表示的仍然是指向文本内部的指针，因此分割和插入内部节点的时间复杂度为O(1)。
&翻译的不错哦!
这时我们处理了abx,并且把剩余后缀数减为2。现在我们需要插入下一个剩余后缀bx。但是在我们做这些之前，我们需要修改活动节点。分割并插入一条边遵循的规则称作规则1，如下，而且它适用于活动节点是根节点的情况（针对下面后续的其他情况，我们将要了解规则3）。规则1如下：
向根节点插入遵循：
活动节点保留为根节点
设置活动边为我们需要插入的新后缀的第一个字符，也就是b。
活动长度减1
因此，新的活动节点三元组(root,'b',1)表明要做的下一个插入在bcabx边，第一个字符之后，即b之后。我们可以确定插入点的时间复杂度为 O(1)，并且检查x是否已经出现在树里。如果它出现在这条边里，我们将结束当前的步骤，保持一切为原样。然而如果x没有出现在这条边里，那么我们分割这条边而插入它：
再此说明，它的时间复杂度为 O(1)，而且我们按照规则1所示把剩余后缀数修改为1，活动节点修改为(root,'x',0)。
&翻译的不错哦!
不过还有一件事情我们必须做。我们称它为规则2：
如果我们分割一条边并插入新的节点，而且如果它不是在当前步骤里创建的第一个节点
的话，我们通过特殊的指针，即后缀连接，把 以前插入的节点和新增的节点连接起来
。后面我们将明白为什么这么做是有用的。这儿我们要明白：后缀连接表示为虚线边：
我们仍然需要插入当前步骤的最终后缀x。因为活动节点的活动长度部分已经减少到0，最终直接插入到根节点上。由于根节点上没有以x开始的边，所以我们插入了新边：
正如你所能看到的，在当前的步骤里插入了所有剩余的后缀。
&翻译的不错哦!
我们设置#=7而前进到步骤7，这将像往常一样自动添加下一个字符a到所有的叶子边上。然后我们试图插入新的最终字符到活动节点（根节点），然后发现它已经存在在这棵树里了。因此我们结束当前的步骤，不插入任何边，并且修改活动点位(root,'a',1)。
设置#=8进入步骤8,我们添加b,像以前所看到的，这仅仅意味着我们修改活动点位(root,'a',2) ,而且不需要做其他事情就增加剩余后缀数。因为b已经出现在这棵树里。然而我们（在 O(1)时间复杂度里）注意到活动节点现在是一条边的结尾。我们通过重置活动节点位(node1,'\0x',0)来体现这个。这儿，我们用node1来指ab边结束的哪个内部节点。
接着设置#=9进入步骤9，我们需要插入'c',这将有助于我们理解的最后一条技巧：
&翻译的不错哦!
第二次扩展：使用后缀连接
像往常一样，#的修改自动给每条是叶子的边添加了c，而且我们转到活动点看是否可以插入'c'。活动点显示'c'已经存在在那条边里，因此我们设置活动点为(node1,'c',1),且增加剩余后缀数，不做任何其他事情。
现在 设置#=10进入步骤10，剩余后缀数是4 ，因此我们首先需要在活动点插入d而实现插入abcd（这条边从第三步骤开始就一直保留着）。
试图在活动点插入d将引起时间复杂度为O(1)的边分割：
分割起始的活动点在上图中标记为红色。 最后一条规则即规则3如下：
分割从不是根节点的活动点开始的边之后，我们应当紧跟着从活动点开始的后缀连接
&，如果存在一条这样的连接，那么重置活动节点使它指向这个节点。如果不存在这
样后缀连接，那么我们设置活动节点为根节点，活动边和活动长度保持不变。
因此活动节点现在是(node2,'c',1),这里node2如下图所示标记为红色：
&翻译的不错哦!
由于abcd的插入已经完成，我们把剩余后缀数减为3，而且考虑当前步骤的下一个剩余后缀bcd。规则3已经设置活动点为右边的节点和边，因此插入bcd可以简单地向活动点插入剩余后缀的最后一个字符d来完成。
要做到这个将引起另一个边分割，根据规则2 ，我们必须创建一条从以前已插入的节点开始的到新建节点的后缀连接：
我们注意到：后缀连接使我们重置了活动点，因为我们能在O(1)复杂度下插入下一个剩余后缀。看看上面的图就可确定标签为ab的真正节点连接到节点b(它的后缀），而节点abc则连接到bc节点。
当前步骤仍然没有结束。现在剩余后缀数是2，我们需要遵循规则3再次重置活动节点。由于当前的活动节点（上图中红色标记的）已经没有后缀连接，我们重置活动节点位根节点。活动节点现在是(root,'c',1)。
&翻译的不错哦!
因此下一个插入发生在根节点的一条边上，以c开始的这条边的标签为:cabxabcd，位于第一个字符之后，即c之后。这将产生另一个分割：
另外，由于这涉及到新的内部节点的创建，我们遵循规则2，设置一条新的从前面已创建的内部节点开始的后缀连接：
（为了制作这些小图，我使用了软件。新的后缀连接使得Dot软件爱你重新布局了已经存在的边，因此仔细地检查并确定上图中插入的唯一的东西就是一条新的后缀连接。）
创建了这条连接，剩余后缀树可设置为1 ，另外由于活动节点是根节点，我们根据规则1修改活动点位(root,'d',0)。这意味着这一步的最后一个插入是向根节点插入单独的d:
&翻译的不错哦!
这是最后一步，至此我们已经完成了后缀树的建立。虽然工作已经完成，但还有许多最后要注意的地方：
在每一步里，我们向前移动#一个位置。这自动在时间复杂度O(1)内修改了所有的叶子结点。
不过，后缀树没有处理 a) 前一步骤保留下来的任何后缀 b)和当前步骤的最后一个字符。
&剩余后缀树告诉我们我们需要做多少个后续的插入。这些插入把一对一对应为在当前位置#结束的字符串的最后的后缀。我们认为是一个接着一个，然后再对它们进行插入。重要的是：每条插入都在O(1)的时间复杂度内完成，因为活动点告诉我们确切的位置，然后我们只需要在活动点增加一个单独的字符。为什& 么？因为其他字符都隐含地包含了（否则活动点将是其他地方）。
&在做了每个这样的插入之后，我们把剩余后缀数减少，并且如果存在后缀的边，就添加一条后缀连接。如果不存在，(根据规则3）我们把活动节点设置为根节点。如果我们已经处在根节点，那么我们根据规则1修改活动节点。在任何情况下，它只花费O(1)的时间复杂度。
在任意插入期间，我们发现我们需要插入的字符已经存在，那么我们不作任何事情而结束当前步骤，甚至在剩余后缀树大于0的情况下。理由是保留的任何插入都是我们试图插入的边的后缀。因此它们所有都隐藏在当前的树里。事实是剩余后缀树大于0确保我们后续对剩余后缀的处理。
& 如果在算法结束时剩余后缀数大于0意味着什么呢？将是这中情况：结束的文本是以前出现在某个地方的这个文本的子字符串。在这种& 情况下，我们必须给这个字符串结尾添加一个额外以前没有出现过的字符。在这样的文档里，通常使用美元符号$作为解决这个问题的& 符号。为什么会发生这种事情呢？---&如果后来我们使用完整的后缀树搜寻后缀，那么我们只有在后缀结束于叶子时才接受搜寻匹配。& 否则我们会得到许多假的匹配，因为后缀树立简单地包含了不是猪字符串的真正后缀的许多这样的字符串。在结束的时候强制剩余后& 缀数为0是确保所有的后缀都结束在叶子节点的重要方法。然而，如果玩么想用这棵树来寻找通常的子字符串，而不仅仅是主字符串的& 后缀，那么根据下面OP的评论的建议，最后一步确实不是必需的。
& 那么，整个算法的复杂性如何呢？如果文本是长度为n的字符组成，那么显然需要n步（或者如果我们增加了没有符号，那么就是n+1 步）。在每个步骤里，我们要么（除了修改变量外）什么都不做，要门我们插入剩余的后缀，每一步都花费O(1)时间复杂度。由于剩余后缀数表明了我们在以前的步骤里不做任何事情的次数，而且现在我们每做一次插入就对剩余后缀数递减，我们做这样的事情& 总的次数准确地说是n(或者n+1)。因此，整体的复杂度是O(n)。
& 然而，有一处小的地方我没有正确地说明： 可能发生这样的情况，我们添加了一条后缀连接，修改活动点，然后发现活动点的活动长度与新的活动节点不能一起正常工作。例如，看看下面这种情况：
& （短划线指的是这棵树的剩余部分，虚线指的是后缀连接。）
&翻译的不错哦!
现在，假设活动节点是(red,'d',3),因此它指向def边的f之后的位置。现在假设我们做了必须的修改，而且现在依据规则3续接了后缀连接并修改了活动节点。新的活动节点是(green,'d',3)。然而从绿色节点出发的d边是de，因此这条边只有2个字符。为了找到正确的活动点，很明显我们需要添加一个到蓝色节点的边，然后重置活动节点为(blue,'f',1)。
在特别糟的情况下，活动长度可以是剩余后缀数那么大，它甚至可以与n一样大。再在找正确的活动节点的时候，这种情况可能刚好发生，我们不仅仅需要跳过一个内部节点长度，不过也许很长，最坏的情况是高达n。由于在每一步里 剩余后缀的插入通常是O(n)，续接了后缀之后的对活动节点的后续调整也是O(n)的复杂度 ，这是否意味着这个算法具有隐藏的O(n
2)的复杂度？
&翻译的不错哦!
不是这样的，理由是如果我们确实需要调整活动节点（例如，如上图所示从绿色节点调整到蓝色节点），那么这就给我们引入了一个拥有自己的后缀连接的新节点，而且活动长度将缩减。当我们沿着后缀连接这个链向下走，我们就要插入剩余的后缀，且只是缩减活动长度，使用这种方法我们可以调整的活动点的数目不可能超过任何给定时刻的活动长度。由于活动长度从来不会超过剩余后缀数，而后缀剩余数不仅仅在每个单一步骤里是O(n)，而且对整个处理过程进行的剩余后缀递增的总数也是O(n)，因此调整活动节点的数目也是以O(n)为界的。
&翻译的不错哦!
不错正在做