首先献上模版
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int Max = 20001;
int num[Max];
int sa[Max], rank[Max], height[Max];
int wa[Max], wb[Max], wv[Max], wd[Max];
int cmp(int *r, int a, int b, int l){
return r[a] == r[b] && r[a+l] == r[b+l];
}
void da(int *r, int n, int m){ // 倍增算法 r为待匹配数组 n为总长度 m为字符范围
int i, j, p, *x = wa, *y = wb, *t;
for(i = 0; i < m; i ++) wd[i] = 0;
for(i = 0; i < n; i ++) wd[x[i]=r[i]] ++;
for(i = 1; i < m; i ++) wd[i] += wd[i-1];
for(i = n-1; i >= 0; i --) sa[-- wd[x[i]]] = i;
for(j = 1, p = 1; p < n; j *= 2, m = p){
for(p = 0, i = n-j; i < n; i ++) y[p ++] = i;
for(i = 0; i < n; i ++) if(sa[i] >= j) y[p ++] = sa[i] - j;
for(i = 0; i < n; i ++) wv[i] = x[y[i]];
for(i = 0; i < m; i ++) wd[i] = 0;
for(i = 0; i < n; i ++) wd[wv[i]] ++;
for(i = 1; i < m; i ++) wd[i] += wd[i-1];
for(i = n-1; i >= 0; i --) sa[-- wd[wv[i]]] = y[i];
for(t = x, x = y, y = t, p = 1, x[sa[0]] = 0, i = 1; i < n; i ++){
x[sa[i]] = cmp(y, sa[i-1], sa[i], j) ? p - 1: p ++;
}
}
}
void calHeight(int *r, int n){ // 求height数组。
int i, j, k = 0;
for(i = 1; i <= n; i ++) rank[sa[i]] = i;
for(i = 0; i < n; height[rank[i ++]] = k){
for(k ? k -- : 0, j = sa[rank[i]-1]; r[i+k] == r[j+k]; k ++);
}
}
int main(){
char str[Max];
int i, m=30, ans,len;
while(scanf("%s",str)!=EOF){
len=strlen(str);
for(i=0;i<=len;i++)num[i]=str[i]-'a'+1;
num[len]=0;
da(num, len + 1, m);
calHeight(num, len);
printf("num: \n");
for(i=0;i<=len;i++){printf("%d ",num[i]);}printf("\n");
printf("sa: \n");
for(i=0;i<=len;i++){printf("%d ",sa[i]);}printf("\n");
printf("rank: \n");
for(i=0;i<=len;i++){printf("%d ",rank[i]);}printf("\n");
printf("height: \n");
for(i=0;i<=len;i++){printf("%d ",height[i]);}printf("\n");
}
return 0;
}
一直不清楚为什么要在最后要加上后缀0,希望有大神解释呃Orz。
这里num[0~n-1]为有效值 就是输入的字符串稍稍转化而成的数组
sa[1~~n]为有效值 sa[i]=a则代表排在第 i 位的是第a个后缀。 a属于[0~~n-1]
rank[0~~n-1]是有效值 rank[i]=b则代表第 i 个后缀排在第b位 b属于[1~~n]
height[2~~n]是有效值 height[i]=c 则代表排在第 i 位的后缀和排在第i-1的后缀的最长前缀长度是c。
- 大小: 10.8 KB
分享到:
相关推荐
后缀数组倍增算法实现 + RMQ问题ST算法实现
后缀数组模板,后缀数组的倍增法实现,名次数组,高度数组
后缀数组的倍增算法和DC3算法的实现以及不可重叠重复子串的问题,很详细的资料
算法文档无代码后缀数组算法文档无代码后缀数组提取方式是百度网盘分享地址
后缀数组是一种较新的建立全文索引的方法。它由某个 文本的所有半无限串(起点在文本任意位置,终点在文本尾的 字符串)字典排序而得,具有较高的检索效率并且更适合如范 围查找、模糊查找等较复杂的查找方式。当前,...
用倍增算法对后缀数组的实现,其中用rmq实现询问两个后缀的最长前缀。
倍增算法对后缀数组构造,height数组构造,lcp构造及O(P+log(n))的字符串搜索,可以运行的源代码,具体对应的算法可在我的博客中查看。
罗穗骞《后缀数组——处理字符串的有力工具》(有算法源码和解题源码) IOI2009论文,有源码,简单易懂,方便学习后缀数组的构造和各种应用。 后缀数组是一种优秀的数据结构,在字符串匹配方面有诸多应用。
树状数组 后缀数组 字典树 多串匹配算法及启示
【摘要】本文介绍后缀数组的基本概念、方法以及应用。首先介绍 O(nlogn)复杂度构造后缀数组的倍增算法,接着介绍了配合后缀数组的最长公共前缀 LCP(Long
dsa-is后缀数组外存算法,是后缀数组内存算法发sa-is的外存实现,该算法能够处理40G以上字符串的后缀数组排序。
学习后缀数组有一点帮组,学习了一周的后缀数组,献给正在为ACM奋斗的同学们
后缀数组的应用受到越来越多人的关注,本文详细介绍了后缀数组的基本原理以及LCP—最长公共前缀。最后给出了几道例题及解析。
【摘要】本文介绍后缀数组的基本概念、方法以及应用。首先介绍 O(nlogn)复杂度构造后缀数组的倍增算法,接着介绍了配合后缀数组的最长公共前缀 LCP(Long
后缀数组——处理字符串的有力工具,国家集训队论文
后缀数组 笔记 后缀数组——处理字符串的有力工具 罗穗骞 后缀数组——处理字符串的有力工具 PPT 后缀数组--许智磊 后缀数组--许智磊 PPT
基于压缩后缀数组实现的一个字符串搜索库,用压缩后缀数组算法实现了一个简单核心的搜索开源库,可以扩展。
比较完整地介绍了后缀数组的概念,用法,解决了诸如最长回文串,最长公共子序列的问题,很值得一看
后缀数组;代码;罗穗骞;题目附代码;OI集训队资料
后缀数组 后缀数组.pdf