后缀数组入门

2020-12-13 05:38

阅读：392

标签：ons names detail i++ problem ble c++ open string

博主睡觉了，明天继续

后缀数组的定义:

后缀数组 (Suffix Array) 指某个字符串的所有后缀按字典排序后得到的数组。数组中只保存后缀开始的位置。

后缀：从某个字符串的某个开始位置到其末尾的字符串子串,包括原串和空字符串。

例子：{ABC}的后缀{ABC},{BC},{C},{}

字典排序: 默认从小到大

技术图片

构造后缀数组:

朴素做法：将n个字符串进行sort排序,时间复杂度\(O(n^2log_2n)\)
倍增数组法: Manber和Myers发明,需要进行 \(log_2n\) 次排序,排序时间复杂度 \(O(nlog_2n)\) ,所以总时间复杂度是 \(O(nlog_2^2n)\) ,可以用基数排序将sort排序进行优化,总时间复杂度优化成 \(O(nlog_2n)\)。
所以一般来说,倍增数组的方法够用了,更快的可以去找[SA-IS 算法]

倍增数组的代码:

未优化代码

#include 
#include 
#include 
#define MAXN 1000
using namespace std;

char str[MAXN];//字符串数组
int sa[MAXN + 1];//后缀数组,+1是为了存储(空字符串)
int rank[MAXN + 1];//Rank[i]第i位开始的子串排名(0~N)
int tmp[MAXN+1];
int k,n;

bool cmp_sa(const int &i,const int &j) {
    if(rank[i] != rank[j])  return rank[i]=k?rank[i+k]:-1;
        int r = n-j>=k?rank[j+k]:-1;
        return l

题目:

Best Cow Line(数据加强版)
未完待续

参考博客和文献:

https://www.cnblogs.com/jinkun113/p/4743694.html
https://www.cnblogs.com/victorique/p/8480093.html
挑战程序设计竞赛（第2版）

后缀数组入门

标签：ons names detail i++ problem ble c++ open string

原文地址：https://www.cnblogs.com/--zz/p/11144860.html

上一篇：转：Web测试需要了解的知识

下一篇：窗体上打个矩形的洞

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：后缀数组入门
文章链接：http://soscw.com/essay/31370.html

亲，登录后才可以留言！

后缀数组入门

博主睡觉了，明天继续

后缀数组的定义:

构造后缀数组:

倍增数组的代码:

题目:

参考博客和文献:

评论

热门文章

推荐文章

最新文章

置顶文章