以下是小编整理的后缀数组，本文共7篇，欢迎阅读分享，希望对您有所帮助。
篇1：后缀数组
后缀数组的模板，这样说明就很详细了吧！
/* * 后缀数组模板-倍增法 * 使用方法： * 1、读取字符串转换成int数组，长度为len，下标从0开始 * 2、在字符串末尾加一字典序最小字符，一般为0,并找到最大的字符设为maxa * 3、调用函数da(num,sa,len+1,maxa+1) * 求得的sa数组的含义： sa[i]为第i字典序后缀字符串的首字母下标 * 4、调用函数build_height(num,sa,len) * 求得的ranking数组的含义： ranking[i]为首字母下标为i的后缀数组的字典序的名次 * 求得的height数组含义： height[i]为第i字典序后缀与第i-1字典序后缀的最长公共前缀，height[1] = 0; * h[i]=height[rank[i]]，也就是suffix(i)和在它前一名的后缀的最长公共前缀，
后缀数组模板
。 * 注意事项： * 转化为数字的字符串最小数值必须不小于1，如果是0的话会Runtime Error，请自重....... */#include篇2：CSU1656: Paper of FlyBrother(后缀数组)
FlyBrother is a superman, therefore he is always busy saving the world.
To graduate from NUDT is boring but necessary for him. Typically We need to post an paper to get Graduate Certificate, however being one superman, FlyBrother wants to make his paper perfect. A paper is a lower case string. To make it perfect, FlyBrother wanna the number of different substrings in the paper. It is quite a silly problem for FlyBrother, but because he is so busy, can you help him to solve it?
篇3：CSU1656: Paper of FlyBrother(后缀数组)
There are several cases. Process till EOF.
For each case, there is a line of lower case string (1<=length<=100000).
篇4：CSU1656: Paper of FlyBrother(后缀数组)
题意： 求不同的字符串个数
思路： 在我的后缀数组题目小结里有一样的的题目，模板题
#include
篇5：面试题[后缀数组]: 最长重复子串
题目：给定一个字符串，求出最长重复子串，
这个题目可以用后缀数组来解：对后缀数组排好序，这样重复的子串就在相邻的后缀中找就可以了。我的C++代码实现如下：
class Solution{public: string LongestRepeatingSubstring(string str) { size_t len = str.size; vector
篇6：poj 3882（Stammering Aliens） 后缀数组 或者 hash
后缀数组： 构建后缀数组，注意要在字符串莫末尾加上一个没出现过的字符，然后可以2分或者直接扫描，直接扫描需要用单调队列来维护
VIEW CODE
#include
字符串hash ： 直接2分了 很好写的
VIEW CODE
#include
篇7：八、数组
数组，顾名思义就是一组同类型的数，
一、数组的声明
声明数组的语法为在数组名后加上用方括号括起来的维数说明。本接仅介绍一维数组。下面是一个整型数组的例子：
int array[10];
这条语句定义了一个具有10个整型元素的名为array的数组。这些整数在内存中是连续存储的。数组的大小等于每个元素的大小乘上数组元素的个数。方括号中的维数表达式可以包含运算符，但其计算结果必须是一个长整型值。这个数组是一维的。
下面这些声明是合法的：
int offset[5+3];
float count[5*2+3];
下面是不合法的：
int n=10;
int offset[n]; /*在声明时，变量不能作为数组的维数*/
二、用下标访问数组元素
int offset[10];
表明该数组是一维数组，里面有10个数，它们分别为offset[0],offset[1],……offset[9]；千万注意，数组的第一个元素下标从0开始。一些刚学编程的人员经常在这儿犯一些错误。
offset[3]=25;
上面的例子是把25赋值给整型数组offset的第四个元素。
在赋值的时候，可以使用变量作为数组下标。
main()
{
int i,offset[10];
for(i=0;i<10;i++) scanf(%d,&offset[i]);
for(i=9;i>=0;i--) printf(%d ,offset[i]);
printf(n);
}
题目的意思是先输入10个整数，存入到数组中，然后反序输出。
三、数组的初始化
前面说了，变量可以在定义的时候初始化，数组也可以。
int array[5]={1,2,3,4,5};
在定义数组时，可以用放在一对大括号中的初始化表对其进行初始化。初始化值的个数可以和数组元素个数一样多。
如果初始化的个数多于元素个数，将产生编译错误；如果少于元素个数，其余的元素被初始化为0。
如果维数表达式为空时，那么将用初始化值的个数来隐式地指定数组元素的个数，如下所式：
int array[]={1,2,3,4,5};
这也表明数组array元素个数为5。
main()
{
int i,array[]={1,3,5,7,9,11};
for(i=0;i<5;i++) printf(%d ,array[i]);
printf(n);
}
最终结果为1 3 5 7 9
四、字符数组
整数和浮点数数组很好理解，在一维数组中，还有一类字符型数组。
char array[5]={'H','E','L','L','O'};
对于单个字符，必须要用单引号括起来。又由于字符和整型是等价的，所以上面的字符型数组也可以这样表示：
char array[5]={72,69,76,76,79}; /*用对应的ASCII码*/
举一个例子：
main()
{
int i;
char array[5]={'H','E','L','L','O'};
for(i=0;i<5;i++) printf(%d ,array[i]);
printf(n);
}
最终的输出结果为72 69 76 76 79
但是字符型数组和整型数组也有不同的地方，看下面的：
char array[]=HELLO;
如果我们能看到内部的话，实际上编译器是这样处理的：
char array[]={'H','E','L','L','O',' '};
看上面最后一个字符' '，它是一个字符常量，Turbo C编译器总是给字符型数组的最后自动加上一个 ，这是字符的结束标志，
所以虽然HELLO只有5个字符，但存入到数组的个数却是6个。但是，数组的长度仍然是5。
int i;
i=strlen(array); /*求字符串的长度，在string.h里面*/
可以看出i仍然是5，表明最后的' '没有算。
#include string.h
main()
{
int i,j;
char array[]=094387fdhgkdladhladaskdh;
j=strlen(array);
for(i=0;i printf(n);
}
其实我们可以根据判断' '来输出字符串，看下面的：
main()
{
int i;
char array[]=094387fdhgkdladhladaskdh;
for(i=0;array[i]!=' ';i++) printf(%c,array[i]);
printf(n);
}
举几个例子：
1.输入10个整数存入数组中，然后把它们从小到大排列并放在同一数组中。(思路：先找出最小的，放在第一个位置，为了防止把原先的数覆盖掉，可以把原先的第一个数和最小数的位置互换)。
main()
{
int array[10];
int i,j,min,stmp;
for(i=0;i<10;i++) scanf(%d,&array[i]);
for(i=0;i<9;i++)
{
min=array[i];
for(j=i+1;j<10;j++)
if(min>array[j]) /*里面的4行语句很重要*/
{
min=array[j];
stmp=array[i];
array[i]=array[j];
array[j]=stmp;
}
}
for(i=0;i<10;i++) printf(%d ,array[i]);
printf(n);
}
分析：先让第一个值作为基准，如果后面有比它小的，那么就把这两个数互换一下，同时把基准换成小的值。两个数互换应该这样(stmp=a;a=b;b=stmp;)，而不是(a=b;b=a;)，想想这是为什么？必须要用一个变量作为桥梁。这种一个一个的把最小的放在前面的排序方法，我们形象的叫做冒泡法。
2.输入一行字符存入数组，然后把他们反序存入到同一数组中。
#include stdio.h
main()
{
char c,stmp,array[80];
int i=0,j;
while((c=getchar())!='n') /*注意这儿的用法*/
array[i++]=c;
array[i]=' '; /*为什么要加' '？是否可以不加？*/
for(j=i-1;j>=i/2;j--)
{
stmp=array[j];
array[j]=array[i-1-j];
array[i-1-j]=stmp;
}
for(i=0;array[i]!=' ';i++) printf(%c,array[i]);
printf(n);
}
3.一个已经排好序的数组，输入一个数，利用二分法把这个数从原数组中删除，数组顺序保持不变。如原数组为1,3,5,7,9,11,13,15,17,19，待删除的数为13，则输出为1,3,5,7,9,11,15,17,19。
二分法：每次都是判断中间的数是否满足要求，若满足则删除，若不满足，则把该数当作边界，然后再找中点。例如这一题，第一次的是10个数的中点，为11，发现11<13，则找11-19的中点15，发现15>13，再找11-15的中点13，正好，则删除。
文档为doc格式
