后缀数组,很精妙的数据结构。
后缀:从母串的某一位置开始到结尾,suffix(i) = Ai,Ai+1...An。
后缀数组:后缀数组SA是个一维数组,它保存1...n的某个排列SA[1],SA[2]...SA[n],并且保证suffix(SA[i])<suffix(SA[i+1]),也就是将S的n个后缀从小到大排好序后的开头位置保存到SA中。
名次数组:名次数组Rank[i]保存的是以i开头的后缀的排名,与SA互为逆。简单的说,后缀数组是“排在第几的是谁”,名次数组是“你排第几”。
为了方便比较,通常在串的末尾添加一个字符,它是从未出现并且最小的字符。
求解后缀数组的算法主要有两种:倍增算法和DC3算法。在这里使用的是许智磊的倍增算法,复杂度为nlogn。
关于详细求解后缀数组的算法,详见许智磊2004国家集训队论文。
后缀数组的应用:
最长公共前缀:先定义height数组,height[i] = suffix(SA[i-1])和suffix(SA[i])的最长公共前缀,也就是排名相邻的两个后缀的最长公共前缀。
例1:最长公共前缀
给定一个串,求任意两个后缀的最长公共前缀。
解:先根据rank确定这两个后缀的排名i和j(i<j),在height数组i+1和j之间寻找最小值。(可以用rmq优化)
例2:最长重复子串(不重叠)(poj1743)
解:二分长度,根据长度len分组,若某组里SA的最大值与最小值的差>=len,则说明存在长度为len的不重叠的重复子串。
例3:最长重复子串(可重叠)
解:height数组里的最大值。这个问题等价于求两个后缀之间的最长公共前缀。
例4:至少重复k次的最长子串(可重叠)(poj3261)
解:二分长度,根据长度len分组,若某组里的个数>=k,则说明存在长度为len的至少重复k次子串。
例5:最长回文子串(ural1297)
给定一个串,对于它的某个子串,正过来写和反过来写一样,称为回文子串。
解:枚举每一位,计算以这个位为中心的的最长回文子串(注意串长要分奇数和偶数考虑)。将整个字符串反转写在原字符串后面,中间用$分隔。这样把问题转化为求某两个后缀的最长公共前缀。
例6:最长公共子串(poj2774)
给定两个字符串s1和s2,求出s1和s2的最长公共子串。
解:将s2连接到s1后,中间用$分隔开。这样就转化为求两个后缀的最长公共前缀,注意不是height里的最大值,是要满足sa[i-1]和sa[i]不能同时属于s1或者s2。
例7:长度不小于k的公共子串的个数(poj3415)
给定两个字符串s1和s2,求出s1和s2的长度不小于k的公共子串的个数(可以相同)。
解:将两个字符串连接,中间用$分隔开。扫描一遍,每遇到一个s2的后缀就统计与前面的s1的后缀能产生多少个长度不小于k的公共子串,这里s1的后缀需要用单调栈来维护。然后对s1也这样做一次。
例8:至少出现在k个串中的最长子串(poj3294)
给定n个字符串,求至少出现在n个串中k个的最长子串。
将n个字符串连接起来,中间用$分隔开。二分长度,根据长度len分组,判断每组的后缀是否出现在不小于k个原串中。
求解后缀数组的模板:
const int N = 20005;//串A的最大长度
const int MAX = 1000100;//串A的最大值
//int n,m,k;
int SA[N], rank[N], height[N], key[N];
int A[N], C[MAX], t1[N+1], t2[N+1];
//倍增法求sa[]-----待排序的字符串放在r 数组中,r[]为整型数组, 从r[0]到r[n-1],长度为n,且最大值小于m
//约定除r[n-1]外所有的r[i]都大于0, r[n-1]=0
//结果放在sa 数组中,从sa[0]到sa[n-1]
//先对所有后缀的第一个字符进行排序(采用挖坑式的基数排序,即统计每个字符的个数,以便在扫描时总能将字符放入合适的位置),放入sa中
void da(int n, int m)
{
int i, j, l, s,*t;
int *X = t1, *Y = t2;
memset(C, 0, sizeof(C));
for (i=0;i<n;i++) C[X[i] = A[i]]++;
for (i=1;i<m;i++) C[i] += C[i-1];
for (i=n-1;i>=0;i--) SA[--C[X[i]]] = i;
for (l=1; l<n; l<<=1)
{
for (i=n-l,j=0;i<n;i++) Y[j++] = i;
for (i=0;i<n;i++) if (SA[i] >= l) Y[j++] = SA[i] - l;
for (i=0;i<n;i++) key[i] = X[Y[i]];
memset(C, 0, sizeof(C));
for (i=0;i<n;i++) C[key[i]]++;
for (i=1;i<m;i++) C[i] += C[i-1];
for (i=n-1;i>=0;i--) SA[--C[key[i]]] = Y[i];
t = X;
X = Y;
Y = t;
X[SA[0]] = j = 0;
for (i=1;i<n;i++)
{
if (Y[SA[i]] != Y[SA[i-1]] || Y[SA[i]+l] != Y[SA[i-1]+l])
j++;
X[SA[i]] = j;
}
m = j + 1;
if (m==n) break;
}
for (i=0;i<n;i++)
rank[SA[i]] = i;
return;
}
//height[i]:suffix(sa[i-1])与suffix(sa[i])的最长公共前缀,即排名相邻的两个后缀的最长公共前缀
void calheight(int n)
{
int i,j,k=0;
for(i=0; i<n; i++)
{
if (k > 0)
--k;
if(rank[i] == 0)
height[0] = 0;
else
{
j = SA[rank[i] - 1];
while(A[i+k] == A[j+k])
k++;
height[rank[i]] = k;
}
}
}
//串A[0]...A[n-1]
da(n,1000001); //m的最大值不超过1,000,000
calheight(n);
- 大小: 44.6 KB
分享到:
相关推荐
罗穗骞《后缀数组——处理字符串的有力工具》(有算法源码和解题源码) IOI2009论文,有源码,简单易懂,方便学习后缀数组的构造和各种应用。...后缀数组是一种优秀的数据结构,在字符串匹配方面有诸多应用。
罗穗骞《后缀数组——处理字符串的有力工具》(有算法源码和解题源码) IOI2009论文,有源码,简单易懂,方便学习后缀数组的构造和各种应用。...后缀数组是一种优秀的数据结构,在字符串匹配方面有诸多应用。
本书是国外数据结构与算法分析方面的经典教材,使用卓越的Java编程语言作为实现工具,讨论数据结构(组织大量数据的方法)和算法分析(对算法运行时间的估计)。随着计算机速度的不断增加和功能的日益强大,人们对...
本书是国外数据结构与算法分析方面的经典教材,使用卓越的Java编程语言作为实现工具,讨论数据结构(组织大量数据的方法)和算法分析(对算法运行时间的估计)。随着计算机速度的不断增加和功能的日益强大,人们对...
常见的数据结构:栈、队列、数组、链表、树、图、字典树(⾼效树形结构)、散列表(哈希表) Java常⽤数据结构(图解): 图⽚源⾃于: 1、栈和队列: 2、栈(stack):先进后出,删除与加⼊均在栈顶操作 栈也称为...
11.7.2 指向结构数组的指针 179 11.7.3 结构指针变量作函数参数 180 11.8 动态存储分配 181 11.9 链表的概念 182 11.10 枚举类型 184 11.10.1 枚举类型的定义和枚举变量的说明 184 11.10.2 枚举类型变量的赋值和使用...
11.7.2 指向结构数组的指针 179 11.7.3 结构指针变量作函数参数 180 11.8 动态存储分配 181 11.9 链表的概念 182 11.10 枚举类型 184 11.10.1 枚举类型的定义和枚举变量的说明 184 11.10.2 枚举类型变量的赋值和使用...
陈 宏 -《数据结构的选择与算法效率——从IOI98试题PICTURE谈起》 来煜坤 -《把握本质,灵活运用——动态规划的深入探讨》 齐 鑫 -《搜索方法中的剪枝优化》 邵 铮 -《数学模型的建立、比较和应用》 石润婷 -...
CS(计算机科学)知识体系 ...6. 编写使用以下各种数据结构的程序:数组、记录、字符串、链表、栈、队列和哈希表。 7. 比较并说明动态和静态数据结构实现的代价和收益的不同。 8. 为指定问题的建模选择适当的数据结构。
4.7.3 后缀数组 4.8 一起来挑战GCJ的题目(3) 4.8.1 Mine Layer 4.8.2 Year of More Code Jam 4.8.3 Football Team 4.8.4 Endless Knight 4.8.5 The Year of Code Jam 阅读 本书中未涉及的拓展主题 书中例题列表 ...
4.压缩文件的算法的数据结构: 为正确解压文件,除了要保存原文件长度外,还要保存原文件中256种字节重复的次数,即权值。定义一个文件头,保存相关的信息: ```c++ struct HEAD { char type[4]; //文件类型 int...
第15章 数据结构 15.1 简介 15.2 自引用类 15.3 动态内存分配 15.4 链表 15.5 堆栈 15.6 队列 15.7 树 小结 术语 自测练习 自测练习答案 练习 特殊小节:建立自己的编译器 第16章 位、字符、字符串和结构 ...
第15章 数据结构 15.1 简介 15.2 自引用类 15.3 动态内存分配 15.4 链表 15.5 堆栈 15.6 队列 15.7 树 小结 术语 自测练习 自测练习答案 练习 特殊小节:建立自己的编译器 第16章 位、字符、字符串和结构 ...
7.1.1 后缀式 7.1.2 图表示法 7.1.3 三地址代码 7.2说明语句 7.2.1 过程中的说明语句 7.2.2保留作用域信息 7.2.3 记录中的域名 7.3赋值语句的翻译 7.3.1 简单算术表达式及赋值语句 7.3.2数组元素的引用 ...
委托是一个数据结构,该数据结构引用一个静态方法,或引用一个对象实例和该对象的实例方法。在 C 或 C 中与委托最接近的是函数指针,但函数指针只能引用静态函数,而委托可以同时引用静态方法和实例方法。在后一种...
3. 关系结构模型:关系式数据结构把一些复杂的数据结构归结为简单的二元关系(即二维表格形式)。常见的有Oracle、mssql、mysql等 二、 主流数据库 数据库名 公司 特点 工作环境 mssql 微软 只能能运行在windows平台,...
(3)但是,当C++窗口类对象销毁时,与之相关的窗口也将销毁,因为它们之间的纽带m_hWnd已经断了 3、示例---在窗口中显示按钮 (1)CButton按钮类继承于CWnd (2)对于一个CButton对象,在定义之后就可以使用了;但是,...