后缀数组-codevs1500

关键词：

      后缀数组的原理很简单，将一个字符串S的所有后缀组成一个字符串数组，并排序，则以后每次判断某个字符串D是不是S的子串只需要strlen(D)*log(strlen(s))的时间复杂度。Codevs1500这题就是一道裸题，考后缀数组的生成，如果一个一个将S的后缀加入到后缀数组中并快速排序需要的时间复杂度为（n的平方*log n)，效率极低。一般可以用倍增法将生成后缀数组的时间复杂度优化到(n*log n*log n)。
      倍增法的思想一开始觉得有点难理解，先只比较每个后缀的第一个字母，得到一个顺序列表，然后再利用之前得到的顺序列表比较每个后缀的前两个字母，然后再利用比较前两个字母得到的顺序列表比较前4个字母。。就这样一直比较到前(2^k)个字母，当(2^k)>=原字符串的长度时即可停止。假设我们当前已经得到了只比较前x个字母的顺序列表，要比较2个后缀前2x个字母的顺序时只需要先比较这两个后缀的前x个字母的顺序，如果相同再比较这两个后缀第x+1个字母到第2x个字母的顺序，由于要比较的字符串的长度都为x，所以可以利用之前得到的只比较后缀的前x个字母的顺序列表来实现快速的比较2个后缀的前2x个字母的顺序，比较一次的时间复杂度为O(1)。

贴个代码：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstdlib>
 4 #include<cstring>
 5 #include<algorithm>
 6 #define maxn 16000
 7 using namespace std;
 8 char s[maxn];
 9 int n,order[2*maxn];
10 struct An_Suffix{
11        int st,len;
12        friend bool operator < (const An_Suffix a,const An_Suffix b){
13               if(a.len==1) return s[a.st]<s[b.st];
14               if(order[a.st]!=order[b.st]) return order[a.st]<order[b.st];
15               return order[a.st+(a.len/2)]<order[b.st+(b.len/2)];
16        }
17        friend bool operator == (const An_Suffix a,const An_Suffix b){
18               if(a.len==1) return s[a.st]==s[b.st];
19               return (order[a.st]==order[b.st] && order[a.st+(a.len/2)]==order[b.st+(b.len/2)]);
20        }
21 }suff[maxn];
22 struct An_Order{
23        int n,order;
24        friend bool operator < (const An_Order a,const An_Order b){
25               return a.order<b.order;
26        }
27 }ans[maxn];
28 void get_order(int len){
29      int order2[maxn];
30      for(int i=0;i<n;i++) suff[i]=((An_Suffix){i,len});
31      sort(suff,suff+n);
32      int t=1;order2[suff[0].st]=t;
33      for(int i=1;i<n;i++){
34              if(!(suff[i-1]==suff[i])) t++;
35              order2[suff[i].st]=t;
36      }
37      for(int i=0;i<n;i++) order[i]=order2[i];
38 }         
39 int main(){
40     scanf("%d",&n);
41     scanf("%s",s);
42     int t=1;
43     while(1){
44              get_order(t);
45              if(t>=n) break;
46              t=t*2;
47     }
48     for(int i=0;i<n;i++) ans[i]=((An_Order){i,order[i]});
49     sort(ans,ans+n);
50     for(int i=0;i<n;i++) printf("%d
",ans[i].n+1);
51     return 0;
52 }

ans是用来记录每个点的顺序的，用来输出答案。数据结构An_Suffix中 重载的“<”用来判断两个后缀在当前的比较长度下的先后顺序，重载的“==”判断两个后缀在当前的比较长度下是否相等。注意order数组一定要开到2*maxn，因为当比较长度为2*（n-1)时，在对以最后一个字符为起点的后缀操作时，有可能访问到order[st+len/2]，此时这个值应当默认为0。

1500后缀排序

1500后缀排序  时间限制:1s 空间限制:128000KB 题目等级:大师Master题解 查看运行结果  题目描述 Description天凯是MIT的新生。Prof. HandsomeG给了他一个长度为n的由小写字母构成的字符串，要求他把该字... 查看详情

codevs3289noip2013花匠

http://codevs.cn/problem/3289/dp转移，树状数组维护前缀max和后缀max进行优化，$O(nlogn)$。#include<cstdio>#include<cstring>#include<algorithm>usingnamespacestd;constintN=100003;intin(){ intk=0,fh=1;charc= 查看详情

树状数组区间修改区间求和codevs1082线段树练习3

http://codevs.cn/problem/1082/【AC】1#include<bits/stdc++.h>2usingnamespacestd;3typedeflonglongll;4constintmaxn=2e5+2;5intn;6lla[maxn];7llc1[maxn];8llc2[maxn];9intlowbit(intx)10{11returnx&-x;1 查看详情

codevs3286火柴排队2013年noip全国联赛提高组树状数组,逆序对

题目：http://codevs.cn/problem/3286/3286火柴排队  2013年NOIP全国联赛提高组 时间限制:1s  空间限制:128000KB  题目等级:钻石Diamond题解   题目描述 Description涵涵有两盒火柴，每盒装有n根火柴，每根... 查看详情

codevs4244平衡树练习

...门:codevs4244平衡树练习 Splay实测指针占用空间大约是数组的3倍，且时间上也慢了差不多1s 数组版评测记录如下 指针版评测记录如下  　　虽然这样。。。　　但是指针写起来就是看着顺眼。。。。/*指针版*/#inc... 查看详情

后缀数组与后缀树

】后缀数组与后缀树【英文标题】：SuffixArraysvsSuffixTrees【发布时间】：2012-06-2623:40:22【问题描述】：我只是想知道，什么时候后缀树优于增强后缀数组。阅读Replacingsuffixtreeswithenhancedsuffixarrays后，我看不到使用后缀树的理由了... 查看详情

后缀数组

后缀数组是处理字符串的有力工具。————罗穗骞·前面的言    在后缀树,后缀自动机以及后缀数组三者中似懂非懂地抉择之后,综合代码量和实用性方面的考虑，你选择了学习后缀数组。本文会像往常一样，以... 查看详情

后缀数组记录(代码片段)

后缀数组参考:彻底弄懂后缀数组后缀数组——处理字符串的有力工具知乎以洛谷P3809【模板】后缀排序为例，看了两天才理解了七成的数据结构┭┮﹏┭┮。先上经典图后缀数组是一个搞出字符串所有后缀的一个字典序排名。字... 查看详情

codevs2492上帝造题的七分钟2(树状数组+并查集)

传送门树状数组模板题。注意优化，假设某个数的值已经是1了的话。那么我们以后就不用对他进行操作了，这个能够用并查集实现。这道题还有个坑的地方，给出查询区间端点的a,b，有可能a>b。#include<cstdio>#include<cm... 查看详情

codevs2498incdecsequence（差分数组）(代码片段)

Description给定一个长度为n的数列a1,a2…an，每次可以选择一个区间[l,r]，使这个区间内的数都加一或者都减一。问至少需要多少次操作才能使数列中的所有数都一样，并求出在保证最少次数的前提下，最终得到的数... 查看详情

codevs2498incdecsequence（差分数组）(代码片段)

Description给定一个长度为n的数列a1,a2…an，每次可以选择一个区间[l,r]，使这个区间内的数都加一或者都减一。问至少需要多少次操作才能使数列中的所有数都一样，并求出在保证最少次数的前提下，最终得到的数... 查看详情

初识后缀数组

...荐博客：https://www.cnblogs.com/zinthos/p/3899725.html 所谓的后缀数组，就是将字符串的n个后缀全部取出来，采用字典序的排序方式，将排序好的后缀开头位置顺次放进数组中。在后缀数组中，有几个关键的变量1.SA数组，若sa[i]=j,所... 查看详情

后缀数组(suffixarray)

参考：Suffixarray-Wiki后缀数组(suffixarray)详解6.3  SuffixArrays-算法红宝书SuffixArray后缀数组基本概念应用：字符串处理、生物信息序列处理后缀：学过英语的都知道什么叫后缀，就是从某个位置开始到字符串结尾的特殊子串，... 查看详情

后缀数组入门——height数组与lcp(代码片段)

前言看这篇博客前，先去了解一下后缀数组的基本操作吧：后缀数组入门（一）——后缀排序。这篇博客的内容，主要建立于后缀排序的基础之上，进一步研究一个(Height)数组以及如何求(LCP)。什么是(LCP)(LCP)，即(LongestCommonPrefix)... 查看详情

后缀数组

　　今天学习了一下后缀数组，感觉是一个较为复杂且精细的数据结构，要理解它最好只抓一些关键的部分。　　首先后缀数组是建立在一个字符串上的数据结构，其存储的元素是字符串的所有后缀，譬如‘abc‘的后缀有‘c‘,... 查看详情

数据结构4——后缀数组

一、相关介绍后缀数组处理字符串的有力工具可以处理后缀自动机解决不了的问题后缀数组被称为SA，后缀自动机被称为SAM。更详细的讲解点击 查看详情

后缀数组

什么是后缀数组后缀数组是处理字符串的有力工具—罗穗骞个人理解：后缀数组是让人蒙逼的有力工具！就像上面那位大神所说的，后缀数组可以解决很多关于字符串的问题，譬如这道题 注意：后缀数组并不是一种算法... 查看详情

后缀数组

先说后缀是啥：后缀就是一个串s从第s[i]一直到串尾就是这个串的一个后缀，记作suffix[i]举个栗子：aacbds的后缀分别为aacbds,acbds,cbds,ds,ds,s（这是回音你懂吗是回音你懂吗回音你懂吗音你懂吗你懂吗懂吗吗）后缀数组实质就是给每... 查看详情