区块链公共前缀性质

⑴ 分布式共识包含哪三种方法

PoW 、PoS 、DPOW都是什么意思？
说到区块链，我们必然会谈及它的共识机制。不了解区块链的共识机制，就无法理解区块链的真正意义。那么，今日份的区块链的共识机制了解一下？
共识机制是什么？
什么是共识？直取它的字面意思，就是"共同的认识".
人与人是不同的，这种不同不仅体现在身材、长相、能力，更体现在文化、观点、想法、利益诉求等等方面。
共识，简而言之，就是一个群体的成员在某一方面达成的一致意见。
我们了解到，信任是社会运转中的一大痛点，银行有自己的信用体系，过去的金融体系服务于只服务于极少的企业家，因为建立信用体系耗资巨大。后来支付宝有了芝麻信用，信用已经关系到生活的很多方面，信用卡额度、花呗额度，芝麻信用高出国还可以免签。我们正享受着信用给我们带来的便捷。
区块链本质是去中心化，去中心化的核心是共识机制，区块链上的共识机制主要解决由谁来构造区块，以及如何维护区块链统一的问题。
区块链共识机制的目标是使所有的诚实节点保存一致的区块链视图，同时满足两个性质：
1）一致性：所有诚实节点保存的区块链的前缀部分完全相同。
2）有效性：由某诚实节点发布的信息终将被其他所有诚实节点记录在自己的区块链中。
区块链的自信任主要体现于分布于区块链中的用户无须信任交易的另一方，也无须信任一个中心化的机构，只需要信任区块链协议下的软件系统即可实现交易。
共识机制是什么？PoW 、PoS 、DPOW都是什么意思？
共识机制的必要性？
分布式系统中，多个主机通过异步通信方式组成网络集群。在这样的一个异步系统中，需要主机之间进行状态复制，以保证每个主机达成一致的状态共识。错误信息可能出现在异步系统内并不断传播，因此需要在默认不可靠的异步网络中定义容错协议，以确保各主机达成安全可靠的状态共识，这就是共识机制诞生的必要性。
这种自信任的前提是区块链的共识机制（consensus），即在一个互不信任的市场中，要想使各节点达成一致的充分必要条件是每个节点出于对自身利益最大化的考虑，都会自发、诚实地遵守协议中预先设定的规则，判断每一笔记录的真实性，最终将判断为真的记录记入区块链之中。attachments-2018-08-9yY7VRHa5b738e3d96021.jpg
换句话说，如果各节点具有各自独立的利益并互相竞争，则这些节点几乎不可能合谋欺骗你，而当节点们在网络中拥有公共信誉时，这一点体现得尤为明显。区块链技术正是运用一套基于共识的数学算法，在机器之间建立"信任"网络，从而通过技术背书而非中心化信用机构来进行全新的信用创造。
当今区块链的几种共识机制介绍
区块链上的共识机制有多种，但任何一种都不是完美无缺，或者说适用于所有应用场景的。
PoW 工作量证明
整个系统中每个节点为整个系统提供计算能力（简称算力），通过一个竞争机制，让计算工作完成最出色的节点获得系统的奖励，即完成新生成货币的分配，简单理解就是多劳多得，bitcoin、LTC等货币型区块链就应用POW机制。
优点
完全去中心化节点自由进出，算法简单，容易实现破坏系统花费的成本巨大，只要网络破坏者的算力不超过网络总算力的50%,网络的交易状态就能达成一致
缺点
浪费能源，这是最大的缺点区块的确认时间难以缩短，如bitcoin每秒只能做7笔交易，不适合商业应用新的区块链必须找到一种不同的散列算法，否则就会面临bitcoin的算力攻击对节点的性能网络环境要求高容易产生分叉，需要等待多个确认无法达成最终一致性
PoS 权益证明
也称股权证明，类似于你把财产存在银行，这种模式会根据你持有加密货币的数量和时间，分配给你相应的利息。
优点
对节点性能要求低，达成共识时间短
缺点
没有最终一致性，需要检查点机制来弥补最终性
DPOW 委托股权证明
DPOW是 PoS 的进化方案，在常规 PoW和 PoS 中，任何一个新加入的区块，都需要被整个网络所有节点做确认，非常影响效率。
DPoS则类似于现代董事会的投票机制，通过选举代表来进行投票和决策。被选举出的n个记账节点来做新区块的创建、验证、签名和相互监督，这样就极大地减少了区块创建和确认所需要消耗的时间和算力成本。
优点
大幅缩小参与验证和记账节点的数量，可以达到秒级的共识验证
缺点
牺牲了去中心化的概念，不适合公有链
PBFT 实用拜占庭容错
实用拜占庭容错机制是一种采用"许可投票、少数服从多数"来选举领导者并进行记账的共识机制，该共识机制允许拜占庭容错，允许强监督节点参与，具备权限分级能力，性能更高，耗能更低，而且每轮记账都会由全网节点共同选举领导者，允许33%的节点作恶，容错率为33%.实用拜占庭容错特别适合联盟链的应用场景。
优点
会背离中心化，加密货币的存在及奖励机制会产生马太效应，让社区中的穷者更穷，富者更富共识效率高，可实现高频交易
缺点
当系统只剩下33%的节点运行时，系统会停止运行
dBFT 授权拜占庭容错
这种机制是用权益来选出记账人，然后记账人之间通过拜占庭容错算法达成共识。授权拜占庭容错机制最核心的一点，就是最大限度地确保系统的最终性，使区块链能够适用于真正的金融应用场景。
优点
专业化的记账人可以容忍任何类型的错误记账由多人协同完成，每一个区块都有最终性，不会分叉算法的可靠性有严格的数学证明
缺点
当三分之一或以上记账人停止工作后，系统将无法提供服务当三分之一或以上记账人联合作恶，可能会使系统出现分叉
Pool 验证池
基于传统的分布式一致性技术，加上数据验证机制。
优点
不需要加密货币也可以工作，在成熟的分布式一致性算法（Pasox、Raft）基础上，实现秒级共识验证。
缺点
去中心化程度不如bitcoin,更适合多方参与的多中心商业模式。
Paxos
这是一种传统的分布式一致性算法，是一种基于选举领导者的共识机制。领导者节点拥有绝对权限，并允许强监督节点参与，其性能高，资源消耗低。所有节点一般有线下准入机制，但选举过程中不允许有作恶节点，不具备容错性。
Paxos算法中将节点分为三种类型：
proposer:提出一个提案，等待大家批准为结案。往往是客户端担任该角色
acceptor:负责对提案进行投票。往往是服务端担任该角色
learner:被告知结案结果，并与之统一，不参与投票过程。可能为客户端或服务端
Paxos 能保证在超过50%的正常节点存在时，系统能达成共识。
瑞波共识机制
瑞波共识算法使一组节点能够基于特殊节点列表形成共识，初始特殊节点列表就像一个俱乐部，要接纳一个新成员，必须由该俱乐部51%的会员投票通过。共识遵循这些核心成员的"51%权利",外部人员则没有影响力。由于该俱乐部由中心化开始，它将一直是中心化的，而如果它开始腐化，股东们什么也做不了。与bitcoin及Peercoin一样，瑞波系统将股东们与其投票权隔开，因此，它比其他系统更中心化。
Peercoin
Peercoin（点点币，PPC），混合了POW工作量证明及POS权益证明方式，其中POW主要用于发行货币，未来预计随着挖矿难度上升，产量降低，系统安全主要由POS维护。
在区块链网络中，由于应用场景的不同，所设计的目标各异，不同的区块链系统采用了不同的共识算法。每种共识算法都不是完美的，都有其优点和局限性。
区块链解决了在不可信信道上传输可信信息、价值转移的问题，而共识机制解决了区块链如何分布式场景下达成一致性的问题。
虽然区块链目前还处于发展的早期，行业发展还面临着一些阻碍，但社会已经足够多地认识到区块链的价值，区块链发展的脚步绝不会停滞不前，行业发展也定会找到突破阻碍的方法。

⑵ 区块链的应用场景有哪些

在甲骨文公司的网站上列出了区块链的十类行业应用场景

包括金融、生产、教育、传媒、娱乐、政府、零售商务、健康、医疗、供应链、保险、公共事业。是不是很高大上？但是我想说的是这些应用场景，在真正高能的区块链应用面前，这些应用场景只能先躲到墙角，瑟瑟发抖。

现在区块链真正高能的应用场景是庞氏应用，俗称“庞氏骗局”。是智能合约型的钱宝、是滚动入金出金的区块链游戏、是以交易为目的的ICO、是全球通用的养老金平台。

庞氏骗局是我们人类最古老的应用场景之一，在互联网出现之后，庞氏骗局已经升级了一次“互联网+”，即“互联网+庞氏骗局”。互联网为庞氏骗局赋能，所以发生了类似钱宝百亿级别的事件，在互联网时代以前，很少有这么大规模的庞氏骗局，通过互联网赋能，通过手机APP入金出金，最后滚动几年，达到了百亿级别的规模。

互联网实现了打破地域限制，物理限制，资金流动限制，传播限制。只要有手机就能玩钱宝APP，人人参与，人人入金，人人出金，涉案人数据说达到百万级别，相对而言，还停留在线下拉人头的传销（庞氏骗局1.0），天天开会洗脑不能停，使用暴力非法手段，简直弱爆了。随着区块链技术的兴起，使用“区块链+”赋能的庞氏骗局，已经不能用如虎添翼来形容了，简直是如鸡变虎。跟互联网一样，“区块链+”技术对应用场景的提升是实打实，庞氏骗局在“互联网+”的二代基础进一步升级，因为有重大的场景提升和改进突破，变成庞氏骗局3.0，其特征主要在以下几方面体现：

1、去中心化，无首脑化。区块链的智能合约是自动运行的，不需要人为干预，也无法被人为中断。代码规则写死，无法篡改。在场景改进上，解决了几千年来，庞氏骗局最大的痛点，即首脑跑路的问题。因为首脑是程序，是代码，区块链的程序可以做到永久存在，没有任何人可以删掉它。我认为这是最大的突破。这个虚拟的首脑是一直在的，跑不掉，也不会跑，也不会改，规则永远不变，坚持庞氏路线一百年一千年一万年。可能会有人说，智能合约是可以迭代的，还可以做手脚留后门。没错，但是也可以做到不需要迭代，即使迭代，也是透明可见的，留了后门，也是一目了然的。这就是区块链智能合约的特点，你在上面作弊，等于在老师眼皮下拿出小抄，这样的智能合约，上线了也没人参与。所以经过技术审查、验证，没有后门，公平规则，不可撤销的智能合约，可以使用区块链技术实现。这样的可靠性，一次验证通过，永久不变。这就是智能合约的确定性，一段程序，一个字符的代码都不变，运行一百万次一万亿次，结果都是一致的确定性。

2、过程透明化。入金人数、地址账号、数额、时间；出金人数、地址账号、数额、时间；全部可见。区块链具有公共的账本功能，全世界人人可以查看，人人查看的账本数据完全一致。钱宝为什么爆仓？因为我们看不到他的后台账号，每天进去多少钱，出来多少钱，具体的每一笔明细。这样在入金之前就能看到兑付能力的评估，而且这个评估结果也是绝对确定性的，即不会在你入金之后发生变化。

3、彻底匿名化。你如果听过什么零知识证明技术。这部分就可以跳过。简单来说，以前我们在数学知识库里面的一些东西，很多发明之后是没有应用场景的，后来被人发现，这些知识拿来做匿名化很好用。区块链里面的密码学技术，能够很好地实现身份隐匿。大家知道，知乎在技术结构上是实现不了真正意义上的匿名的，区块链可以。

4、规则公开，对所有人公平。入金一块钱，返利出金十块钱，所有人都是这个规则，永久不变。你入金一块钱，先去给前面的人出金，然后后面的人入金，再给你出金。公平吧？这一点，我反思了很多次，觉得还是很公平。

5、可持续迭代。低级的庞氏骗局，首脑、产品设计者、利益分配者、利益获得者经常是四位一体，而区块链庞氏骗局，可以完全逻辑分离四个角色。实现永续迭代。通过基于社会化的协作，这些项目可以永续迭代下去。围绕比特币进行开发，还在不断更新代码的资深工程师现在有400名，这些人可以谁也不认识谁，只要这个应用有价值，就可以一直迭代下去。哪个中心化的项目可以做到，就算是BAT级别的公司，也聘不到这么多分散在全球的专业人士。这种社会化迭代方式不受某个具体的人和具体的组织的变动的影响。

“区块链”赋能的庞氏骗局，使用的区块链技术范围各不相同，因为这个领域的技术还在不断更新，像智能合约这一块的应用是这两年才多起来。最早的区块链应用是比特币，有人认为比特币本身就具有庞氏骗局的特征，2013年我写过一个回答就隐晦地指出，这种新型的庞氏骗局杀伤力会很大，因为具有无首脑、账本公开、不会跑路、规则公开公平的特征。后来，我也发现，身边的很多人，对庞氏骗局的喜好，远高于对区块链技术的兴趣。一听说比特币不是庞氏骗局，在我开始讲点区块链的技术之前，一般就默默走开了，反之，你跟他说是庞氏骗局，然后他们接着就会问，在哪里买？当然，比特币算不算庞氏骗局是有很多争议的，因为比特币的实际应用场景是一直在扩展的。

而在ICO热潮里面，有很多空气币，则是如假包换的庞氏骗局，是没有任何应用场景的，这些空气币，买的人大概也知道是庞氏骗局，但是看包装得不错，就买了。这样的空气币估计有几百种上千种。涉案范围遍布全球，金额何止百亿。这些ICO使用智能合约进行认筹和分配，然后自行到二级市场流通。这种情况下，出金是没有保证的，有人亏得血本无归。很多人区块链专业人士，一直想跟这些应用划清界线，因为这些空气币虽然用了部分区块链的技术，但背后还是一个中心化的组织或者个人，网络节点极少，用户入金的时候直接汇聚给了某个组织或个人（因此会被卷跑），但无疑，空气币还是利用区块链进行入金和发筹，解决了一部分跑路的问题，提升了庞氏骗局的范围和传播能力。这是客观发生的情况。

而从今年开始，随着技术的进展，利用智能合约实现更加去中心化的庞氏骗局，开始浮出水面。入金和发筹使用智能合约锁定，完成完整的入金、认筹、出金闭环。已经可以是很纯粹的区块链应用，有一些区块链游戏，已经可以很大方地承认，发行后公开声称自己就是一个庞氏游戏，他说：你看，规则透明、代码可见、入金合约锁定、不会跑路、无人为干预、自动出金。早玩早收益。这是很关键的一步突破，公开承认自己是庞氏骗局，这种玩法是以前庞氏骗局1.0和2.0做不到的（不敢公开承认自己是庞氏骗局）。厉害了。玩法简单粗暴啊。

这就解决了以前庞氏骗局推广过程的重大障碍，以前是靠洗脑拉人头，现在靠代码说话。你看“这段程序不会自己跑路吧，里面没有后门吧？首脑已经消失了吧？中本聪被抓住也不影响程序继续执行吧？”所以区块链庞氏骗局第一批上钩的是看得懂代码的码农，然后这些码农再站出来说，经技术验证，确实是这么一个效果，带动其他不看代码的人加入。

区块链除了实现娱乐、赌博、诈骗性质的庞氏骗局应用场景之外，在涉及国计民生、公共事业性质的庞氏骗局应用场景也有大展拳脚的机会，甚至可以极大地增强人民获得感、幸福感，以及实打实改善人民生活。比如基于区块链的国家或全球公共养老金平台应用，这种平台因为基于区块链，可以解决养老金的几大弊病：

1、资金挪用问题。账本公开，资金非中心化锁定，没有人可以解锁，除了符合规则的领取人可以出金。没有挪用可能性。

2、通货膨胀问题。现行的养老金体制每年都要根据通货膨胀等一系列复杂的算法，调整系数，调整完之后，领取者经常会不满意，因为总额上升了，但是购买力下降了。利用虚拟货币无法增发的特性，可以克制通胀率，保证领取到的都是真金白银。

3、不可预测的问题。我们很难预测30年后养老金的出金情况，通过智能合约则可以实现提前预测。刺激缴纳积极性。

4、政策漏洞和公平问题。任何养老金政策面向的群体多样化，里面会有不公平情况，任何人都想着少缴多拿、晚缴早提。区块链的透明度细化到每个账号，而不是一套笼统的政策，堵住实施过程的漏洞。每个人都是一样的，多缴多出，早缴早出。甚至可以继承，永不丢失。

这么干极大地减轻了国家管理养老金的负担和成本，现有的养老金制度能做到的事情，使用区块链技术之后，仍然能够做到，比如国家补贴，往合约里打钱就行了，打进去就锁定，不会有假，比如强制缴纳，每笔记录也都是真实可追查的。总而言之，现有的体制和规则全部可以上链，在不影响现有效果的基础上，提升了效率和产出水平，保证公平，而且因为减少了庞大的管理体系的成本，每个人能领取到的绝对数说不定能上升一大截，这就起到了实打实改善人民生活的效果，还是那句话，有获得感、幸福感的提升。在养老金这件事情上，我们信任的主体从单一的国家政府，变成国家政府+区块链，50%以上的过程变成固定的软件程序，我们这样不是更相信了吗？如果100%实现链上养老金系统，那么甚至可以打破国家范围限制，由一段诚实的、不会作弊、无法篡改的代码来实现，自动入金、自动出金，信任它，就像信任一个死人，不会有错误。

下一代人养这一代人的设计，是我们人类进化的一个伟大发明，加速了社会发展的速度，这样表面看，好像地球上的最后一代人会比较吃亏，其实不会，因为地球的最后一代人也不一定知道自己是最后一代人（可能最后几秒钟知道，但又如何），何况地球都消失了，最后一代人还需要出金养老吗？显然，不需要啊。

庞氏骗局，最大的弊端就是中途跑路，资金断裂，区块链在解决这个问题上，有明确的技术解法，而且还能被证明、也能够被证伪，所以，这个技术是科学的。弊端被消除，好处逐步显现，庞氏骗局未来还将取得更大的发展。

我也想问一个问题，在人类历史上，有没有哪些原来是负面的、或者没用的东西，后来随着技术的发展，弊端被消除或规避，作用被发掘，然后变得越来越有用，越来越重要？

⑶ 什么是区块链共识

所谓“共识机制”，是通过特殊节点的投票，在很短的时间内完成对交易的验证和确认；对一笔交易，如果利益不相干的若干个节点能够达成共识，我们就可以认为全网对此也能够达成共识。再通俗一点来讲，如果中国一名微博大V、美国一名虚拟币玩家、一名非洲留学生和一名欧洲旅行者互不相识，但他们都一致认为你是个好人，那么基本上就可以断定你这人还不坏。
区块链作为一种按时间顺序存储数据的数据结构，可支持不同的共识机制。共识机制是区块链技术的重要组件。区块链共识机制的目标是使所有的诚实节点保存一致的区块链视图，同时满足两个性质：
1）一致性。所有诚实节点保存的区块链的前缀部分完全相同。
2）有效性。由某诚实节点发布的信息终将被其他所有诚实节点记录在自己的区块链中。

⑷ 成立一家新加坡基金会来做区块链常见的问题有哪些

区块链与基金会之间存在着哪些联系会遇到哪些问题
很多人在做区块链的时候，通常会注册一家基金会来与普通公司一起运行，目前选择新加坡基金会的比较，那么，注册一家新加坡基金会来做区块链经常会遇到的问题有哪些呢，下面根据一些客户关心的问题整理一些分享给大家
1、注册费用是包含白皮书的费用吗？
答：没有的，法律顾问是个性化的业务，费用需要了解项目而定。法律顾问，可以全流程进行服务。包括白皮书的法律条文修改、针对代币非证券属性等相关法律法规出具专业法律意见。ico发币过程中的法律咨询。

2、关于新加坡基金会的。为什么要有一家公司来运营，和基金会什么关系？为什么不直接注册一家公司进行ico及对接交易所？
答：基金会本来就是公益组织，公共部门，用基金会做区块链的发行是比较有利于吸引投资和技术开发的，也可通过普通公司直接进行ICO，这个要具体看客户自己想怎么操作。
3、ico不就是募集资金的一种方式吗
答：是的。用已有实际价值的货币，参与项目的众筹，换得项目新发的加密币。筹款者的好处是得到了开展项目的资金，而参与者则希望项目成功，这样手中的新发加密币很可能会升值，从而套利。所谓 ICO，就是投资者使用比特币等现成的虚拟数字货币，去换取ICO项目发行的新代币。因为新币种拥有者少、价格波动大，在交易所的卖出价格很可能比发行价高得多。而ICO项目发起方利用融来的传统数字货币，在交易所换回人民币等法定货币，再投入到指定的技术项目中。
4、为什么不通过常见的渠道来募集资金
答：常见渠道门槛低，没有监管部门。风险较大。
5、怎么设立交易所？
答：可根据自身情况自行选择交易所，一般要选择有比较强的数字资产安全管理经验。平台有很多。
6、为什么要做法律意见书？
根据新加坡金融法和证券法，如果包含有证券性质的虚拟货币需要申请特殊金融牌照，所以需要证明该项目不包含有证券性质，那么就需要律师出具TOKEN非证券化法律意见书，以及证明该项目合法合规的白皮书合规法律意见书，这两者是大部分客户都要做的。
7、注册的新加坡基金会主体在银行开户怎么开？
首先，注册公众非盈利基金会是没有必要开户的，开了也没有用，因为基金会本身的性质就是非盈利的，到次年审计的时候无法和金融管理局解释银行账户上的款项收支呢？第二，银行对客户是有挑选的，如果告诉银行是做区块链的，银行是不会接受开户的；第三，无论是私募还是公募，募集来的都是以太坊比特币这样的虚拟货币，普通银行账户是收不了这些币种的，所以我这边不建议到银行去开户。

⑸ 什么是后缀数组 求字符串匹配

后缀数组
在字符串处理当中，后缀树和后缀数组都是非常有力的工具，其中后缀树大家了解得比较多，关于后缀数组则很少见于国内的资料。其实后缀数组是后缀树的一个非常精巧的替代品，它比后缀树容易编程实现，能够实现后缀树的很多功能而时间复杂度也不太逊色，并且，它比后缀树所占用的空间小很多。可以说，在信息学竞赛中后缀数组比后缀树要更为实用。因此在本文中笔者想介绍一下后缀数组的基本概念、构造方法，以及配合后缀数组的最长公共前缀数组的构造方法，最后结合一些例子谈谈后缀数组的应用。
基本概念
首先明确一些必要的定义：
字符集 一个字符集∑是一个建立了全序关系的集合，也就是说，∑中的任意两个不同的元素α和β都可以比较大小，要么α<β，要么β<α（也就是α>β）。字符集∑中的元素称为字符。
字符串 一个字符串S是将n个字符顺次排列形成的数组，n称为S的长度，表示为len(S)。S的第i个字符表示为S。
子串 字符串S的子串S[i..j]，i≤j，表示S串中从i到j这一段，也就是顺次排列S,S[i+1],...,S[j]形成的字符串。
后缀 后缀是指从某个位置i开始到整个串末尾结束的一个特殊子串。字符串S的从i开头的后缀表示为Suffix(S,i)，也就是Suffix(S,i)=S[i..len(S)]。
关于字符串的大小比较，是指通常所说的“字典顺序”比较，也就是对于两个字符串u、v，令i从1开始顺次比较u和v，如果相等则令i加1，否则若u<v则认为u<v，u>v则认为u>v（也就是v<u），比较结束。如果i>len(u)或者i>len(v)仍未比较出结果，那么若len(u)<len(v)则认为u<v，若len(u)=len(v)则认为u=v，若len(u)>len(v)则u>v。
从字符串的大小比较的定义来看，S的两个开头位置不同的后缀u和v进行比较的结果不可能是相等，因为u=v的必要条件len(u)=len(v)在这里不可能满足。
下面我们约定一个字符集∑和一个字符串S，设len(S)=n，且S[n]='$'，也就是说S以一个特殊字符'$'结尾，并且'$'小于∑中的任何一个字符。除了S[n]之外，S中的其他字符都属于∑。对于约定的字符串S，从位置i开头的后缀直接写成Suffix(i)，省去参数S。
后缀数组 后缀数组SA是一个一维数组，它保存1..n的某个排列SA[1],SA[2],...SA[n]，并且保证 Suffix(SA)<Suffix(SA[i+1]),1≤i<n。也就是将S的n个后缀从小到大进行排序之后把排好序的后缀的开头位置顺次放入SA中。
名次数组 名次数组Rank=SA-1，也就是说若SA=j，则Rank[j]=i，不难看出Rank保存的是Suffix(i)在所有后缀中从小到大排列的“名次”。
构造方法
如何构造后缀数组呢？最直接最简单的方法当然是把S的后缀都看作一些普通的字符串，按照一般字符串排序的方法对它们从小到大进行排序。
不难看出，这种做法是很笨拙的，因为它没有利用到各个后缀之间的有机联系，所以它的效率不可能很高。即使采用字符串排序中比较高效的Multi-key Quick Sort，最坏情况的时间复杂度仍然是O(n2)的，不能满足我们的需要。
下面介绍倍增算法(Doubling Algorithm)，它正是充分利用了各个后缀之间的联系，将构造后缀数组的最坏时间复杂度成功降至O(nlogn)。
对一个字符串u，我们定义u的k-前缀
定义k-前缀比较关系<k、=k和≤k：
设两个字符串u和v，
u<kv 当且仅当 uk<vk
u=kv 当且仅当 uk=vk
u≤kv 当且仅当 uk≤vk
直观地看这些加了一个下标k的比较符号的意义就是对两个字符串的前k个字符进行字典序比较，特别的一点就是在作大于和小于的比较时如果某个字符串的长度不到k也没有关系，只要能够在k个字符比较结束之前得到第一个字符串大于或者小于第二个字符串就可以了。
根据前缀比较符的性质我们可以得到以下的非常重要的性质：
性质1.1 对k≥n，Suffix(i)<kSuffix(j) 等价于 Suffix(i)<Suffix(j)。
性质1.2 Suffix(i)=2kSuffix(j)等价于
Suffix(i)=kSuffix(j) 且 Suffix(i+k)=kSuffix(j+k)。
性质1.3 Suffix(i)<2kSuffix(j) 等价于
Suffix(i)<kS(j) 或 (Suffix(i)=kSuffix(j) 且 Suffix(i+k)<kSuffix(j+k))。
这里有一个问题，当i+k>n或者j+k>n的时候Suffix(i+k)或Suffix(j+k)是无明确定义的表达式，但实际上不需要考虑这个问题，因为此时Suffix(i)或者Suffix(j)的长度不超过k，也就是说它们的k-前缀以'$'结尾，于是k-前缀比较的结果不可能相等，也就是说前k个字符已经能够比出大小，后面的表达式自然可以忽略，这也就看出我们规定S以'$'结尾的特殊用处了。
定义k-后缀数组SAk保存1..n的某个排列SAk[1],SAk[2],…SAk[n]使得Suffix(SAk) ≤kSuffix(SAk[i+1]),1≤i<n。也就是说对所有的后缀在k-前缀比较关系下从小到大排序，并且把排序后的后缀的开头位置顺次放入数组SAk中。
定义k-名次数组Rankk，Rankk代表Suffix(i)在k-前缀关系下从小到大的“名次”，也就是1加上满足Suffix(j)<kSuffix(i)的j的个数。通过SAk很容易在O(n)的时间内求出Rankk。
假设我们已经求出了SAk和Rankk，那么我们可以很方便地求出SA2k和Rank2k，因为根据性质1.2和1.3，2k-前缀比较关系可以由常数个k-前缀比较关系组合起来等价地表达，而Rankk数组实际上给出了在常数时间内进行<k和=k比较的方法，即：
Suffix(i)<kSuffix(j) 当且仅当 Rankk<Rankk[j]
Suffix(i)=kSuffix(j) 当且仅当 Rankk=Rankk[j]
因此，比较Suffix(i)和Suffix(j)在k-前缀比较关系下的大小可以在常数时间内完成，于是对所有的后缀在≤k关系下进行排序也就和一般的排序没有什么区别了，它实际上就相当于每个Suffix(i)有一个主关键字Rankk和一个次关键字Rankk[i+k]。如果采用快速排序之类O(nlogn)的排序，那么从SAk和Rankk构造出SA2k的复杂度就是O(nlogn)。更聪明的方法是采用基数排序，复杂度为O(n)。
求出SA2k之后就可以在O(n)的时间内根据SA2k构造出Rank2k。因此，从SAk和Rankk推出SA2k和Rank2k可以在O(n)时间内完成。
下面只有一个问题需要解决：如何构造出SA1和Rank1。这个问题非常简单：因为<1，=1和≤1这些运算符实际上就是对字符串的第一个字符进行比较，所以只要把每个后缀按照它的第一个字符进行排序就可以求出SA1，不妨就采用快速排序，复杂度为O(nlogn)。
于是，可以在O(nlogn)的时间内求出SA1和Rank1。
求出了SA1和Rank1，我们可以在O(n)的时间内求出SA2和Rank2，同样，我们可以再用O(n)的时间求出SA4和Rank4，这样，我们依次求出：
SA2和Rank2，SA4和Rank4，SA8和Rank8，……直到SAm和Rankm，其中m=2k且m≥n。而根据性质1.1，SAm和SA是等价的。这样一共需要进行logn次O(n)的过程，因此
可以在O(nlogn)的时间内计算出后缀数组SA和名次数组Rank。
最长公共前缀
现在一个字符串S的后缀数组SA可以在O(nlogn)的时间内计算出来。利用SA我们已经可以做很多事情，比如在O(mlogn)的时间内进行模式匹配，其中m,n分别为模式串和待匹配串的长度。但是要想更充分地发挥后缀数组的威力，我们还需要计算一个辅助的工具——最长公共前缀（Longest Common Prefix）。
对两个字符串u,v定义函数lcp(u,v)=max{i|u=iv}，也就是从头开始顺次比较u和v的对应字符，对应字符持续相等的最大位置，称为这两个字符串的最长公共前缀。
对正整数i,j定义LCP(i,j)=lcp(Suffix(SA),Suffix(SA[j])，其中i,j均为1至n的整数。LCP(i,j)也就是后缀数组中第i个和第j个后缀的最长公共前缀的长度。
关于LCP有两个显而易见的性质：
性质2.1 LCP(i,j)=LCP(j,i)
性质2.2 LCP(i,i)=len(Suffix(SA))=n-SA+1
这两个性质的用处在于，我们计算LCP(i,j)时只需要考虑i<j的情况，因为i>j时可交换i,j，i=j时可以直接输出结果n-SA+1。
直接根据定义，用顺次比较对应字符的方法来计算LCP(i,j)显然是很低效的，时间复杂度为O(n)，所以我们必须进行适当的预处理以降低每次计算LCP的复杂度。
经过仔细分析，我们发现LCP函数有一个非常好的性质：
设i<j，则LCP(i,j)=min{LCP(k-1,k)|i+1≤k≤j} （LCP Theorem）
要证明LCP Theorem，首先证明LCP Lemma:
对任意1≤i<j<k≤n，LCP(i,k)=min{LCP(i,j),LCP(j,k)}
证明：设p=min{LCP(i,j),LCP(j,k)}，则有LCP(i,j)≥p,LCP(j,k)≥p。
设Suffix(SA)=u,Suffix(SA[j])=v,Suffix(SA[k])=w。
由u=LCP(i,j)v得u=pv；同理v=pw。
于是Suffix(SA)=pSuffix(SA[k])，即LCP(i,k)≥p。 (1)
又设LCP(i,k)=q>p，则
u[1]=w[1],u[2]=w[2],...u[q]=w[q]。
而min{LCP(i,j),LCP(j,k)}=p说明u[p+1]≠v[p+1]或v[p+1]≠w[q+1]，
设u[p+1]=x,v[p+1]=y,w[p+1]=z，显然有x≤y≤z，又由p<q得p+1≤q，应该有x=z，也就是x=y=z，这与u[p+1]≠v[p+1]或v[p+1]≠w[q+1]矛盾。
于是，q>p不成立，即LCP(i,k)≤p。 (2)
综合(1),(2)知 LCP(i,k)=p=min{LCP(i,j),LCP(j,k)}，LCP Lemma得证。
于是LCP Theorem可以证明如下：
当j-i=1和j-i=2时，显然成立。
设j-i=m时LCP Theorem成立，当j-i=m+1时，
由LCP Lemma知LCP(i,j)=min{LCP(i,i+1),LCP(i+1,j)}，
因j-(i+1)≤m，LCP(i+1,j)=min{LCP(k-1,k)|i+2≤k≤j}，故当j-i=m+1时，仍有
LCP(i,j)=min{LCP(i,i+1),min{LCP(k-1,k)|i+2≤k≤j}}=min{LCP(k-1,k}|i+1≤k≤j)
根据数学归纳法，LCP Theorem成立。
根据LCP Theorem得出必然的一个推论：
LCP Corollary 对i≤j<k，LCP(j,k)≥LCP(i,k)。
定义一维数组height，令height=LCP(i-1,i)，1<i≤n，并设height[1]=0。
由LCP Theorem，LCP(i,j)=min{height[k]|i+1≤k≤j}，也就是说，计算LCP(i,j)等同于询问一维数组height中下标在i+1到j范围内的所有元素的最小值。如果height数组是固定的，这就是非常经典的RMQ（Range Minimum Query）问题。
RMQ问题可以用线段树或静态排序树在O(nlogn)时间内进行预处理，之后每次询问花费时间O(logn)，更好的方法是RMQ标准算法，可以在O(n)时间内进行预处理，每次询问可以在常数时间内完成。
对于一个固定的字符串S，其height数组显然是固定的，只要我们能高效地求出height数组，那么运用RMQ方法进行预处理之后，每次计算LCP(i,j)的时间复杂度就是常数级了。于是只有一个问题——如何尽量高效地算出height数组。
根据计算后缀数组的经验，我们不应该把n个后缀看作互不相关的普通字符串，而应该尽量利用它们之间的联系，下面证明一个非常有用的性质：
为了描述方便，设h=height[Rank]，即height=h[SA]。h数组满足一个性质：
性质3 对于i>1且Rank>1，一定有h≥h[i-1]-1。
为了证明性质3，我们有必要明确两个事实：
设i<n,j<n，Suffix(i)和Suffix(j)满足lcp(Suffix(i),Suffix(j)>1，则成立以下两点：
Fact 1 Suffix(i)<Suffix(j) 等价于 Suffix(i+1)<Suffix(j+1)。
Fact 2 一定有lcp(Suffix(i+1),Suffix(j+1))=lcp(Suffix(i),Suffix(j))-1。
看起来很神奇，但其实很自然：lcp(Suffix(i),Suffix(j))>1说明Suffix(i)和Suffix(j)的第一个字符是相同的，设它为α，则Suffix(i)相当于α后连接Suffix(i+1)，Suffix(j)相当于α后连接Suffix(j+1)。比较Suffix(i)和Suffix(j)时，第一个字符α是一定相等的，于是后面就等价于比较Suffix(i)和Suffix(j)，因此Fact 1成立。Fact 2可类似证明。
于是可以证明性质3：
当h[i-1]≤1时，结论显然成立，因h≥0≥h[i-1]-1。
当h[i-1]>1时，也即height[Rank[i-1]]>1，可见Rank[i-1]>1，因height[1]=0。
令j=i-1,k=SA[Rank[j]-1]。显然有Suffix(k)<Suffix(j)。
根据h[i-1]=lcp(Suffix(k),Suffix(j))>1和Suffix(k)<Suffix(j)：
由Fact 2知lcp(Suffix(k+1),Suffix(i))=h[i-1]-1。
由Fact 1知Rank[k+1]<Rank，也就是Rank[k+1]≤Rank-1。
于是根据LCP Corollary，有
LCP(Rank-1,Rank)≥LCP(Rank[k+1],Rank)
=lcp(Suffix(k+1),Suffix(i))
=h[i-1]-1
由于h=height[Rank]=LCP(Rank-1,Rank)，最终得到 h≥h[i-1]-1。
根据性质3，可以令i从1循环到n按照如下方法依次算出h：
若Rank=1，则h=0。字符比较次数为0。
若i=1或者h[i-1]≤1，则直接将Suffix(i)和Suffix(Rank-1)从第一个字符开始依次比较直到有字符不相同，由此计算出h。字符比较次数为h+1，不超过h-h[i-1]+2。
否则，说明i>1，Rank>1，h[i-1]>1，根据性质3，Suffix(i)和Suffix(Rank-1)至少有前h[i-1]-1个字符是相同的，于是字符比较可以从h[i-1]开始，直到某个字符不相同，由此计算出h。字符比较次数为h-h[i-1]+2。
设SA[1]=p，那么不难看出总的字符比较次数不超过
也就是说，整个算法的复杂度为O(n)。
求出了h数组，根据关系式height=h[SA]可以在O(n)时间内求出height数组，于是
可以在O(n)时间内求出height数组。
结合RMQ方法，在O(n)时间和空间进行预处理之后就能做到在常数时间内计算出对任意(i,j)计算出LCP(i,j)。
因为lcp(Suffix(i),Suffix(j))=LCP(Rank,Rank[j])，所以我们也就可以在常数时间内求出S的任何两个后缀之间的最长公共前缀。这正是后缀数组能强有力地处理很多字符串问题的重要原因之一。

⑹ 后缀数组的height数组有什么性质

（1）height 数组：定义height[i]=suffix(SA[i-1])和suffix(SA[i])的最长公共前缀，也就是排名相邻的两个后缀的最长公共前缀的长度 。
（2）h[i]=height[rank[i]]，也就是suffix(i)和排序后在它前一名的后缀的最长公共前缀的长度。
（3）函数lcp(u,v)=max{i|u=v}，也就是从头开始顺次比较u和v的对应字符，对应字符持续相等的最大位置，称为这两个字符串u,v的最长公共前缀的长度。
（4）LCP(i,j)：对正整数i,j 定义LCP(i,j)=lcp(Suffix(SA[i]),Suffix(SA[j])，其中i,j 均为1至n的整数。LCP(i,j)也就是后缀数组中第i个和第j个后缀的最长公共前缀的长度。

⑺ 区块链发币一定要注册基金会吗有什么要求

区块链，是由一组技术实现的大规模、去中心化的经济组织模式。区块链引起广泛关注在于它改变了许多领域的原有经济组织模式。人们现在探索区块链在经济各领域的应用，本质上也是在寻找利用区块链调整或创新原有的企业、产业、区域的经济组织方式，寻找降低成本、提高收益的新途径。将区块链作为一种经济组织模式，向下可以延伸到它的实现技术，向上可以拓展到对社会组织和社会意识的影响，更容易理解区块链带来的复杂社会影响。
现在国内已经禁止发币了，但是海外政策宽松，不过做区块链技术的公司都会要求发币方有主体公司作为依托，才会去合作。所以大多数做区块链行业的都有注册一个主体的基金会。
英国、美国、开曼、新加坡、甚至马耳他都可以注册基金会，那么这些地区有哪些区别呢？英美现在主要是做非盈利性基金会，类似于国内的社会团体，单纯募zi避税是没有问题的，但是发币做法律合规是做不了的；开曼基金会又叫做有限合伙（ELP），是一个普通合伙人（GP）和一个或多个有限合伙人（LP）组成，这样的组合成本上势必会增加，目前就是阿里、京东、网络等一些大集团为了上市所选择的；至于马耳他，政策及其不稳定，而且连收款都受中国制裁，所以大多数人都是“望而却步”。
所以现在新加坡还是区块链落户的中心地区，这主要得益于新加坡宽松的经济环境和良好的政策，在新加坡注册基金会，第一离中国近，有什么消息可以及时把控；第二新加坡非盈利性质基金会是免税的；第三大众的选择，许多知名的代币发行都选择先注册新加坡基金会；第四发行代币需要做法律合规，这一块新加坡有非常完善的服务体系。
注册新加坡基金会所需要的资料：
1、2名注册人身份证（扫描件），在新加坡无犯罪记录，年满十八周岁即可。
2、公司名称：以LTD.结尾，可以加FUND/FOUNDATION。
3、注册资本：1新币，政府规定。
4、公司性质：公众担保（非盈利）。
5、注册时间：10-25个工作日。

⑻ 国家集训队论文

后缀数组

【作者】
安徽省芜湖市第一中学 许智磊

【摘要】
本文介绍后缀数组的基本概念、方法以及应用。
首先介绍O(nlogn)复杂度构造后缀数组的倍增算法，接着介绍了配合后缀数组的最长公共前缀 LCP（Longest Common Prefix）的计算方法，并给出一个线性时间内计算height数组（记录跨度为1的LCP值的数组）的算法。最后介绍两个应用后缀数组的例子：多模式串的模式匹配以及求最长回文子串。

【关键字】
字符串 后缀 k-前缀比较关系
后缀数组 名次数组 后缀树 倍增算法 基数排序
最长公共前缀 RMQ问题 模式匹配 回文串 最长回文子串

【正文】
在字符串处理当中，后缀树和后缀数组都是非常有力的工具，其中后缀树大家了解得比较多，关于后缀数组则很少见于国内的资料。其实后缀数组是后缀树的一个非常精巧的替代品，它比后缀树容易编程实现，能够实现后缀树的很多功能而时间复杂度也不太逊色，并且，它比后缀树所占用的空间小很多。可以说，在信息学竞赛中后缀数组比后缀树要更为实用。因此在本文中笔者想介绍一下后缀数组的基本概念、构造方法，以及配合后缀数组的最长公共前缀数组的构造方法，最后结合一些例子谈谈后缀数组的应用。

基本概念

首先明确一些必要的定义：

字符集 一个字符集∑是一个建立了全序关系的集合，也就是说，∑中的任意两个不同的元素α和β都可以比较大小，要么α<β，要么β<α（也就是α>β）。字符集∑中的元素称为字符。
字符串 一个字符串S是将n个字符顺次排列形成的数组，n称为S的长度，表示为len(S)。S的第i个字符表示为S[i]。
子串 字符串S的子串S[i..j]，i≤j，表示S串中从i到j这一段，也就是顺次排列S[i],S[i+1],...,S[j]形成的字符串。
后缀 后缀是指从某个位置i开始到整个串末尾结束的一个特殊子串。字符串S的从i开头的后缀表示为Suffix(S,i)，也就是Suffix(S,i)=S[i..len(S)]。

关于字符串的大小比较，是指通常所说的“字典顺序”比较，也就是对于两个字符串u、v，令i从1开始顺次比较u[i]和v[i]，如果相等则令i加1，否则若u[i]<v[i]则认为u<v，u[i]>v[i]则认为u>v（也就是v<u），比较结束。如果i>len(u)或者i>len(v)仍比较出结果，那么若len(u)<len(v)则认为u<v，若len(u)=len(v)则认为u=v，若len(u)>len(v)则u>v。
从字符串的大小比较的定义来看，S的两个开头位置不同的后缀u和v进行比较的结果不可能是相等，因为u=v的必要条件len(u)=len(v)在这里不可能满足。

下面我们约定一个字符集∑和一个字符串S，设len(S)=n，且S[n]='$'，也就是说S以一个特殊字符'$'结尾，并且'$'小于∑中的任何一个字符。除了S[n]之外，S中的其他字符都属于∑。对于约定的字符串S，从位置i开头的后缀直接写成Suffix(i)，省去参数S。

后缀数组 后缀数组SA是一个一维数组，它保存1..n的某个排列SA[1],SA[2],...SA[n]，并且保证 Suffix(SA[i])<Suffix(SA[i+1]),1≤i<n。也就是将S的n个后缀从小到大进行排序之后把排好序的后缀的开头位置顺次放入SA中。
名次数组 名次数组Rank=SA-1，也就是说若SA[i]=j，则Rank[j]=i，不难看出Rank[i]保存的是Suffix(i)在所有后缀中从小到大排列的“名次”。

构造方法
如何构造后缀数组呢？最直接最简单的方法当然是把S的后缀都看作一些普通的字符串，按照一般字符串排序的方法对它们从小到大进行排序。
不难看出，这种做法是很笨拙的，因为它没有利用到各个后缀之间的有机联系，所以它的效率不可能很高。即使采用字符串排序中比较高效的Multi-key Quick Sort，最坏情况的时间复杂度仍然是O(n2)的，不能满足我们的需要。
下面介绍倍增算法(Doubling Algorithm)，它正是充分利用了各个后缀之间的联系，将构造后缀数组的最坏时间复杂度成功降至O(nlogn)。

对一个字符串u，我们定义u的k-前缀

定义k-前缀比较关系<k、=k和≤k：
设两个字符串u和v，
u<kv 当且仅当 uk<vk
u=kv 当且仅当 uk=vk
u≤kv 当且仅当 uk≤vk

直观地看这些加了一个下标k的比较符号的意义就是对两个字符串的前k个字符进行字典序比较，特别的一点就是在作大于和小于的比较时如果某个字符串的长度不到k也没有关系，只要能够在k个字符比较结束之前得到第一个字符串大于或者小于第二个字符串就可以了。
根据前缀比较符的性质我们可以得到以下的非常重要的性质：
性质1.1 对k≥n，Suffix(i)<kSuffix(j) 等价于 Suffix(i)<Suffix(j)。
性质1.2 Suffix(i)=2kSuffix(j)等价于
Suffix(i)=kSuffix(j) 且 Suffix(i+k)=kSuffix(j+k)。
性质1.3 Suffix(i)<2kSuffix(j) 等价于
Suffix(i)<kS(j) 或 (Suffix(i)=kSuffix(j) 且 Suffix(i+k)<kSuffix(j+k))。
这里有一个问题，当i+k>n或者j+k>n的时候Suffix(i+k)或Suffix(j+k)是无明确定义的表达式，但实际上不需要考虑这个问题，因为此时Suffix(i)或者Suffix(j)的长度不超过k，也就是说它们的k-前缀以'$'结尾，于是k-前缀比较的结果不可能相等，也就是说前k个字符已经能够比出大小，后面的表达式自然可以忽略，这也就看出我们规定S以'$'结尾的特殊用处了。

定义k-后缀数组SAk保存1..n的某个排列SAk[1],SAk[2],…SAk[n]使得Suffix(SAk[i]) ≤kSuffix(SAk[i+1]),1≤i<n。也就是说对所有的后缀在k-前缀比较关系下从小到大排序，并且把排序后的后缀的开头位置顺次放入数组SAk中。
定义k-名次数组Rankk，Rankk[i]代表Suffix(i)在k-前缀关系下从小到大的“名次”，也就是1加上满足Suffix(j)<kSuffix(i)的j的个数。通过SAk很容易在O(n)的时间内求出Rankk。
假设我们已经求出了SAk和Rankk，那么我们可以很方便地求出SA2k和Rank2k，因为根据性质1.2和1.3，2k-前缀比较关系可以由常数个k-前缀比较关系组合起来等价地表达，而Rankk数组实际上给出了在常数时间内进行<k和=k比较的方法，即：
Suffix(i)<kSuffix(j) 当且仅当 Rankk[i]<Rankk[j]
Suffix(i)=kSuffix(j) 当且仅当 Rankk[i]=Rankk[j]
因此，比较Suffix(i)和Suffix(j)在k-前缀比较关系下的大小可以在常数时间内完成，于是对所有的后缀在≤k关系下进行排序也就和一般的排序没有什么区别了，它实际上就相当于每个Suffix(i)有一个主关键字Rankk[i]和一个次关键字Rankk[i+k]。如果采用快速排序之类O(nlogn)的排序，那么从SAk和Rankk构造出SA2k的复杂度就是O(nlogn)。更聪明的方法是采用基数排序，复杂度为O(n)。
求出SA2k之后就可以在O(n)的时间内根据SA2k构造出Rank2k。因此，从SAk和Rankk推出SA2k和Rank2k可以在O(n)时间内完成。
下面只有一个问题需要解决：如何构造出SA1和Rank1。这个问题非常简单：因为<1，=1和≤1这些运算符实际上就是对字符串的第一个字符进行比较，所以只要把每个后缀按照它的第一个字符进行排序就可以求出SA1，不妨就采用快速排序，复杂度为O(nlogn)。
于是，可以在O(nlogn)的时间内求出SA1和Rank1。
求出了SA1和Rank1，我们可以在O(n)的时间内求出SA2和Rank2，同样，我们可以再用O(n)的时间求出SA4和Rank4，这样，我们依次求出：
SA2和Rank2，SA4和Rank4，SA8和Rank8，……直到SAm和Rankm，其中m=2k且m≥n。而根据性质1.1，SAm和SA是等价的。这样一共需要进行logn次O(n)的过程，因此
可以在O(nlogn)的时间内计算出后缀数组SA和名次数组Rank。

最长公共前缀
现在一个字符串S的后缀数组SA可以在O(nlogn)的时间内计算出来。利用SA我们已经可以做很多事情，比如在O(mlogn)的时间内进行模式匹配，其中m,n分别为模式串和待匹配串的长度。但是要想更充分地发挥后缀数组的威力，我们还需要计算一个辅助的工具——最长公共前缀（Longest Common Prefix）。
对两个字符串u,v定义函数lcp(u,v)=max{i|u=iv}，也就是从头开始顺次比较u和v的对应字符，对应字符持续相等的最大位置，称为这两个字符串的最长公共前缀。
对正整数i,j定义LCP(i,j)=lcp(Suffix(SA[i]),Suffix(SA[j])，其中i,j均为1至n的整数。LCP(i,j)也就是后缀数组中第i个和第j个后缀的最长公共前缀的长度。
关于LCP有两个显而易见的性质：
性质2.1 LCP(i,j)=LCP(j,i)
性质2.2 LCP(i,i)=len(Suffix(SA[i]))=n-SA[i]+1
这两个性质的用处在于，我们计算LCP(i,j)时只需要考虑i<j的情况，因为i>j时可交换i,j，i=j时可以直接输出结果n-SA[i]+1。

直接根据定义，用顺次比较对应字符的方法来计算LCP(i,j)显然是很低效的，时间复杂度为O(n)，所以我们必须进行适当的预处理以降低每次计算LCP的复杂度。
经过仔细分析，我们发现LCP函数有一个非常好的性质：
设i<j，则LCP(i,j)=min{LCP(k-1,k)|i+1≤k≤j} （LCP Theorem）

要证明LCP Theorem，首先证明LCP Lemma:
对任意1≤i<j<k≤n，LCP(i,k)=min{LCP(i,j),LCP(j,k)}
证明：设p=min{LCP(i,j),LCP(j,k)}，则有LCP(i,j)≥p,LCP(j,k)≥p。
设Suffix(SA[i])=u,Suffix(SA[j])=v,Suffix(SA[k])=w。
由u=LCP(i,j)v得u=pv；同理v=pw。
于是Suffix(SA[i])=pSuffix(SA[k])，即LCP(i,k)≥p。 (1)

又设LCP(i,k)=q>p，则
u[1]=w[1],u[2]=w[2],...u[q]=w[q]。
而min{LCP(i,j),LCP(j,k)}=p说明u[p+1]≠v[p+1]或v[p+1]≠w[q+1]，
设u[p+1]=x,v[p+1]=y,w[p+1]=z，显然有x≤y≤z，又由p<q得p+1≤q，应该有x=z，也就是x=y=z，这与u[p+1]≠v[p+1]或v[p+1]≠w[q+1]矛盾。
于是，q>p不成立，即LCP(i,k)≤p。 (2)
综合(1),(2)知 LCP(i,k)=p=min{LCP(i,j),LCP(j,k)}，LCP Lemma得证。

于是LCP Theorem可以证明如下：
当j-i=1和j-i=2时，显然成立。
设j-i=m时LCP Theorem成立，当j-i=m+1时，
由LCP Lemma知LCP(i,j)=min{LCP(i,i+1),LCP(i+1,j)}，
因j-(i+1)≤m，LCP(i+1,j)=min{LCP(k-1,k)|i+2≤k≤j}，故当j-i=m+1时，仍有
LCP(i,j)=min{LCP(i,i+1),min{LCP(k-1,k)|i+2≤k≤j}}=min{LCP(k-1,k}|i+1≤k≤j)
根据数学归纳法，LCP Theorem成立。

根据LCP Theorem得出必然的一个推论：
LCP Corollary 对i≤j<k，LCP(j,k)≥LCP(i,k)。

定义一维数组height，令height[i]=LCP(i-1,i)，1<i≤n，并设height[1]=0。
由LCP Theorem，LCP(i,j)=min{height[k]|i+1≤k≤j}，也就是说，计算LCP(i,j)等同于询问一维数组height中下标在i+1到j范围内的所有元素的最小值。如果height数组是固定的，这就是非常经典的RMQ（Range Minimum Query）问题。
RMQ问题可以用线段树或静态排序树在O(nlogn)时间内进行预处理，之后每次询问花费时间O(logn)，更好的方法是RMQ标准算法，可以在O(n)时间内进行预处理，每次询问可以在常数时间内完成。
对于一个固定的字符串S，其height数组显然是固定的，只要我们能高效地求出height数组，那么运用RMQ方法进行预处理之后，每次计算LCP(i,j)的时间复杂度就是常数级了。于是只有一个问题——如何尽量高效地算出height数组。
根据计算后缀数组的经验，我们不应该把n个后缀看作互不相关的普通字符串，而应该尽量利用它们之间的联系，下面证明一个非常有用的性质：
为了描述方便，设h[i]=height[Rank[i]]，即height[i]=h[SA[i]]。h数组满足一个性质：
性质3 对于i>1且Rank[i]>1，一定有h[i]≥h[i-1]-1。
为了证明性质3，我们有必要明确两个事实：

设i<n,j<n，Suffix(i)和Suffix(j)满足lcp(Suffix(i),Suffix(j)>1，则成立以下两点：
Fact 1 Suffix(i)<Suffix(j) 等价于 Suffix(i+1)<Suffix(j+1)。
Fact 2 一定有lcp(Suffix(i+1),Suffix(j+1))=lcp(Suffix(i),Suffix(j))-1。
看起来很神奇，但其实很自然：lcp(Suffix(i),Suffix(j))>1说明Suffix(i)和Suffix(j)的第一个字符是相同的，设它为α，则Suffix(i)相当于α后连接Suffix(i+1)，Suffix(j)相当于α后连接Suffix(j+1)。比较Suffix(i)和Suffix(j)时，第一个字符α是一定相等的，于是后面就等价于比较Suffix(i)和Suffix(j)，因此Fact 1成立。Fact 2可类似证明。

于是可以证明性质3：
当h[i-1]≤1时，结论显然成立，因h[i]≥0≥h[i-1]-1。
当h[i-1]>1时，也即height[Rank[i-1]]>1，可见Rank[i-1]>1，因height[1]=0。
令j=i-1,k=SA[Rank[j]-1]。显然有Suffix(k)<Suffix(j)。
根据h[i-1]=lcp(Suffix(k),Suffix(j))>1和Suffix(k)<Suffix(j)：
由Fact 2知lcp(Suffix(k+1),Suffix(i))=h[i-1]-1。
由Fact 1知Rank[k+1]<Rank[i]，也就是Rank[k+1]≤Rank[i]-1。
于是根据LCP Corollary，有
LCP(Rank[i]-1,Rank[i])≥LCP(Rank[k+1],Rank[i])
=lcp(Suffix(k+1),Suffix(i))
=h[i-1]-1
由于h[i]=height[Rank[i]]=LCP(Rank[i]-1,Rank[i])，最终得到 h[i]≥h[i-1]-1。

根据性质3，可以令i从1循环到n按照如下方法依次算出h[i]：
若Rank[i]=1，则h[i]=0。字符比较次数为0。
若i=1或者h[i-1]≤1，则直接将Suffix(i)和Suffix(Rank[i]-1)从第一个字符开始依次比较直到有字符不相同，由此计算出h[i]。字符比较次数为h[i]+1，不超过h[i]-h[i-1]+2。
否则，说明i>1，Rank[i]>1，h[i-1]>1，根据性质3，Suffix(i)和Suffix(Rank[i]-1)至少有前h[i-1]-1个字符是相同的，于是字符比较可以从h[i-1]开始，直到某个字符不相同，由此计算出h[i]。字符比较次数为h[i]-h[i-1]+2。

设SA[1]=p，那么不难看出总的字符比较次数不超过

也就是说，整个算法的复杂度为O(n)。
求出了h数组，根据关系式height[i]=h[SA[i]]可以在O(n)时间内求出height数组，于是
可以在O(n)时间内求出height数组。

结合RMQ方法，在O(n)时间和空间进行预处理之后就能做到在常数时间内计算出对任意(i,j)计算出LCP(i,j)。
因为lcp(Suffix(i),Suffix(j))=LCP(Rank[i],Rank[j])，所以我们也就可以在常数时间内求出S的任何两个后缀之间的最长公共前缀。这正是后缀数组能强有力地处理很多字符串问题的重要原因之一。

后缀数组的应用
下面结合两个例子谈谈如何运用后缀数组。

例一 多模式串的模式匹配问题

后缀数组与后缀树的比较