`
yzmduncan
  • 浏览: 325994 次
  • 性别: Icon_minigender_1
  • 来自: 武汉
文章分类
社区版块
存档分类
最新评论

数据结构之——后缀数组

阅读更多

    后缀数组,很精妙的数据结构。

    后缀:从母串的某一位置开始到结尾,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
分享到:
评论

相关推荐

    11.罗穗骞《后缀数组——处理字符串的有力工具》.zip

    罗穗骞《后缀数组——处理字符串的有力工具》(有算法源码和解题源码) IOI2009论文,有源码,简单易懂,方便学习后缀数组的构造和各种应用。...后缀数组是一种优秀的数据结构,在字符串匹配方面有诸多应用。

    罗穗骞《后缀数组——处理字符串的有力工具》(有算法源码和解题源码)

    罗穗骞《后缀数组——处理字符串的有力工具》(有算法源码和解题源码) IOI2009论文,有源码,简单易懂,方便学习后缀数组的构造和各种应用。...后缀数组是一种优秀的数据结构,在字符串匹配方面有诸多应用。

    数据结构与算法分析 Java语言描述(原书第3版)扫描版 高清带书签 附源码

    本书是国外数据结构与算法分析方面的经典教材,使用卓越的Java编程语言作为实现工具,讨论数据结构(组织大量数据的方法)和算法分析(对算法运行时间的估计)。随着计算机速度的不断增加和功能的日益强大,人们对...

    数据结构与算法分析_Java语言描述(第3版)

    本书是国外数据结构与算法分析方面的经典教材,使用卓越的Java编程语言作为实现工具,讨论数据结构(组织大量数据的方法)和算法分析(对算法运行时间的估计)。随着计算机速度的不断增加和功能的日益强大,人们对...

    数据结构--数据结构的组织方法.pdf

    常见的数据结构:栈、队列、数组、链表、树、图、字典树(⾼效树形结构)、散列表(哈希表) Java常⽤数据结构(图解): 图⽚源⾃于: 1、栈和队列: 2、栈(stack):先进后出,删除与加⼊均在栈顶操作 栈也称为...

    谭浩强C语言程序设计,C++程序设计,严蔚敏数据结构,高一凡数据结构算法分析与实现.rar

    11.7.2 指向结构数组的指针 179 11.7.3 结构指针变量作函数参数 180 11.8 动态存储分配 181 11.9 链表的概念 182 11.10 枚举类型 184 11.10.1 枚举类型的定义和枚举变量的说明 184 11.10.2 枚举类型变量的赋值和使用...

    谭浩强C语言程序设计,C++程序设计,严蔚敏数据结构,高一凡数据结构算法分析与实现.rar )

    11.7.2 指向结构数组的指针 179 11.7.3 结构指针变量作函数参数 180 11.8 动态存储分配 181 11.9 链表的概念 182 11.10 枚举类型 184 11.10.1 枚举类型的定义和枚举变量的说明 184 11.10.2 枚举类型变量的赋值和使用...

    IOI国家集训队论文集1999-2019

    陈 宏 -《数据结构的选择与算法效率——从IOI98试题PICTURE谈起》 来煜坤 -《把握本质,灵活运用——动态规划的深入探讨》 齐 鑫 -《搜索方法中的剪枝优化》 邵 铮 -《数学模型的建立、比较和应用》 石润婷 -...

    计算机要学哪些东西----(还有附赠哦)

    CS(计算机科学)知识体系 ...6. 编写使用以下各种数据结构的程序:数组、记录、字符串、链表、栈、队列和哈希表。 7. 比较并说明动态和静态数据结构实现的代价和收益的不同。 8. 为指定问题的建模选择适当的数据结构。

    挑战程序设计竞赛(第2版)

    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 阅读 本书中未涉及的拓展主题 书中例题列表 ...

    基于C++、文件操作和Huffman算法实现图片压缩源码+使用说明+详细注释+sln解决方案.zip

    4.压缩文件的算法的数据结构: 为正确解压文件,除了要保存原文件长度外,还要保存原文件中256种字节重复的次数,即权值。定义一个文件头,保存相关的信息: ```c++ struct HEAD { char type[4]; //文件类型 int...

    C++大学教程,一本适合初学者的入门教材(part2)

    第15章 数据结构 15.1 简介 15.2 自引用类 15.3 动态内存分配 15.4 链表 15.5 堆栈 15.6 队列 15.7 树 小结 术语 自测练习 自测练习答案 练习 特殊小节:建立自己的编译器 第16章 位、字符、字符串和结构 ...

    C++大学教程,一本适合初学者的入门教材(part1)

    第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#学习笔记.txt

    委托是一个数据结构,该数据结构引用一个静态方法,或引用一个对象实例和该对象的实例方法。在 C 或 C 中与委托最接近的是函数指针,但函数指针只能引用静态函数,而委托可以同时引用静态方法和实例方法。在后一种...

    oracle学习文档 笔记 全面 深刻 详细 通俗易懂 doc word格式 清晰 连接字符串

    3. 关系结构模型:关系式数据结构把一些复杂的数据结构归结为简单的二元关系(即二维表格形式)。常见的有Oracle、mssql、mysql等 二、 主流数据库 数据库名 公司 特点 工作环境 mssql 微软 只能能运行在windows平台,...

    MFC的程序框架剖析

    (3)但是,当C++窗口类对象销毁时,与之相关的窗口也将销毁,因为它们之间的纽带m_hWnd已经断了 3、示例---在窗口中显示按钮 (1)CButton按钮类继承于CWnd (2)对于一个CButton对象,在定义之后就可以使用了;但是,...

Global site tag (gtag.js) - Google Analytics