后缀数组

2021-05-17 06:31

阅读：505

标签：cpp insert const 点数据 std 简单 class i++ 代码

对于后缀有关的东西，本人一无所知。

如果你点击进来这博客，那请你谨慎阅读。

本菜鸡在开开心心刷沈大佬给我拉的铜牌题专题的时候，突然遇到了一到后缀自动机的题，不过，我完全不会。上网搜索资料的时候，我看到了后缀数组，后缀自动机，后缀树这几个东西，我也不知道他们是干什么的，也不知道他们的难度如何，于是就找了一个看起来最简单的来学一下。

此博客会基于挑战，谈一些自己现在的理解。由于是本菜鸡的初步理解，再次重申，请谨慎阅读！！

所谓后缀数组，就是先拿到某个数组的所有后缀，给他们加上一个标号id，再将他们排个序，最后得到id的序列就是后缀数组。

请大家看一下我的暴力代码：

#include
#include
#include
using namespace std;
string s;
const int maxn = 10086;
struct node
{
    string ss;
    int id;
}sa[maxn];

bool cmp(node x,node y)
{
    return x.ss>s;
    int l=s.length();
    for(int  i=l;i>=0;i--){
        sa[i].ss=sa[i+1].ss;
        sa[i].ss.insert(sa[i].ss.begin(),s[i]);//得到后缀
        sa[i].id=i;//打上标号
    }

    sort(sa,sa+l+1,cmp);//根据后缀排序

    //最后，id顺序就是后缀数组的内容
    for(int i=0;i

　　这样的暴力时间复杂度取决于string的插入操作，其他的地方就只有一个sort有nlog(n)的复杂度，本菜鸡并不知道string的复杂度是多少，不过据我分析，应该是n²的。

就此而言，整个算法的时间复杂度就应该是n²的。

所以，挑战上给我们介绍了一种nlog²n的算法。

整个算法的过程挑战已经说得非常清楚了，在P378.所以我会再次讲解一下他的代码。

一下代码是一个一个字直接打出来，但愿我没有抄错，不过测了一点数据，和暴力的输出是一样的。

//未完待续

后缀数组

标签：cpp insert const 点数据 std 简单 class i++ 代码

原文地址：https://www.cnblogs.com/ZGQblogs/p/9746886.html

上一篇：python+selenium环境搭建

下一篇：ECharts.js学习（三）

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

亲，登录后才可以留言！

后缀数组

评论

热门文章

推荐文章

最新文章

置顶文章