正文

[后缀数组]学习笔记未完

Candy?  Candy?  2022-08-19  635

关键词：

飒飒飒飒飒飒飒飒飒飒

研究了好长时间....(诶好像莫比乌斯反演时也说过这句话)

参考资料：

1.http://wenku.baidu.com/link?url=Beh6Asxvtm7M2QY5kiPyKKaP87xvBrNBKW9LXOeGKm-WM4GoUM3opnHZ8z-DahF7TRaLZZ4cpUe6jfFF064XUEmAiIDF7t90CpgNfSC3_Pq

2.http://www.cnblogs.com/staginner/archive/2012/02/02/2335600.html

3.http://www.xymlife.com/2016/01/16/后缀数组小结/#more

【概念】：（论文里很清楚了，这里说自己的理解）

1. 后缀：后缀是指从某个位置i开始到结束的子串。Suffix(i)=r[i..len(r)]

后缀i是从i开始的子串

2. 后缀数组： 后缀数组 SA 是一个一维数组，它保存1..n 的某个排列 SA[1]，SA[2]， ……，SA[n]，并且保证Suffix(SA[i]) < Suffix(SA[i+1])，1 ≤ i < n。也就是将 S 的 n 个后缀从小到大进行排序之后把排好序的后缀的开头位置顺次放入SA 中。

后缀排序之后的结果

sa[i]是排名为i的后缀的起点下标(开始位置)

3. 名次数组：名次数组 Rank[i] 保存的是 Suffix(i) 在所有后缀中从小到大排列的 “ 名次 ” 。
rank[i]是后缀i的名次(从i开始的子串位置i的子串)

【倍增算法】：

见论文描述

一张图，每个位置开始长度为j的排序，然后用两个j组成2*j排序.........

【实现】：

排序使用计数排序，

n是字符串长度，m是字符大小上限

a是要排序数组 sa后缀数组

c是计数排序用的

r为“第一关键字key1”的名次数组(类似于给每个位置开始的子串分配一个名次/权值一开始一个字符r[i]=a[i])

k为“第二关键字key2”的排序结果

k[i]表示的是按key2排序后第i名整个子串(key1+key2)开始的位置，不是key2开始的位置

可以发现 key1开始位置+j=key2开始位置

先给单个字符计数排序

然后从j=1开始(每次循环是把两个j合成j<<1)

p最后是当前不同的子串(不一定是后缀)的个数，p==n就没必要继续排序了(已经可以区分每个位置开始的字符串的大小关系了)

1.给key2排序：先处理没有key2的(n-j+1...n)，再通过上一次排序后的sa得到k(上次sa就是长度j的结果，这次的一个关键字长度也是j，只要sa[i]-j变成key1开始的位置就行了)

2.这时r[k[i]]就是key2排第i名的key1的权值，k[i]就是i的开始位置，计数排序，结果用sa保存

3.更新r为长度j<<1时的名次，把r复制给k，这个名次会有相同的，应该算一个，用离散化去重的写法....如何判断相同:先判断是不是都有key2，有一个没有key2的话两个一定不相同(长度就不可能相同了啊)，再分别判断两个关键字是否相同(这时的k是长度j时的名次，判断就行了)

「这里和论文里不太一样，他的做法是加了一个0....」

【求LCP】

height数组:定义 height[i]=suffix(sa[i-1])和 suffix(sa[i])的最长公共前缀

排名i和排名i-1后缀的LCP

对于第i名和第j名，他们的LCP就是RMQ{height[i+1],height[i+2],...,height[j]}

定义h[i]=height[rank[i]]

第i个后缀和在它的前一名的后缀的LCP。

性质：h[i]>=h[i-1]-1

设 suffix(k)是排在 suffix(i-1)前一名的后缀，则它们的最长公共前缀是 h[i-1]。那么 suffix(k+1)将排在 suffix(i)的前面(这里要求 h[i-1]>1，如果 h[i-1]≤1，原式显然成立 )并且 suffix(k+1)和 suffix(i)的最长公共前缀是 h[i-1]-1，所以 suffix(i)和在它前一名的后缀的最长公共前缀至少是 h[i-1]- 1。按照h[1],h[2],......,h[n]的顺序计算,并利用 h 数组的性质，时间复杂度可 以降为 O(n)。

证明

也就是说第i个和他的前一名的LCP至少是i-1和它的前一名的LCP-1，直观上理解，i-1往后一位(长度-1)就是i啊

实现上，并没有必要弄一个h[]，只需要按照h的顺序(也就是原来1..n的顺序)算就行了

注意：m的大小最后会为n，所以c数组至少为n

    void getHeight(){
        int k=0;
        for(int i=1;i<=n;i++) rnk[sa[i]]=i;
        for(int i=1;i<=n;i++){
            if(k) k--;
            if(rnk[i]==1) continue;
            int j=sa[rnk[i]-1];
            while(i+k<=n&&j+k<=n&&s[i+k]==s[j+k]) k++;
            height[rnk[i]]=k;
        }
    }
    inline bool cmp(int *r,int a,int b,int j){
        return a+j<=n&&b+j<=n&&r[a]==r[b]&&r[a+j]==r[b+j];
    }
    void getSA(){ m=300
        int *r=t1,*k=t2;
        for(int i=0;i<=m;i++) c[i]=0;
        for(int i=1;i<=n;i++) c[r[i]=s[i]]++;
        for(int i=1;i<=m;i++) c[i]+=c[i-1];
        for(int i=n;i>=1;i--) sa[c[r[i]]--]=i;
        
        for(int j=1;j<=n;j<<=1){
            int p=0;
            for(int i=n-j+1;i<=n;i++) k[++p]=i;
            for(int i=1;i<=n;i++) if(sa[i]>j) k[++p]=sa[i]-j;
            
            for(int i=0;i<=m;i++) c[i]=0;
            for(int i=1;i<=n;i++) c[r[k[i]]]++;
            for(int i=1;i<=m;i++) c[i]+=c[i-1];
            for(int i=n;i>=1;i--) sa[c[r[k[i]]]--]=k[i];
            
            swap(r,k);p=0;r[sa[1]]=++p;
            for(int i=2;i<=n;i++) r[sa[i]]=cmp(k,sa[i],sa[i-1],j)?p:++p;
            if(p>=n) break;m=p;
        }
    }
    
    int lcp(int x,int y){
        x=rnk[x];y=rnk[y];
        if(x>y) swap(x,y);x++;
        int t=Log[y-x+1];
        return min(mn[x][t],mn[y-Pow[t]+1][t]);
    }

后缀数组学习笔记

现在来看倍增算法是非常好理解的。直接放一篇blog写的挺好的：http://www.cnblogs.com/zinthos/p/3899725.html虽然理论复杂度是$O(nlogn)$，但其中各种细节优化确实十分有必要的。给自己放一个倍增的模板，有空填DC3的坑1#include<cstdio>2#... 查看详情

cad二次开发学习笔记-未完待续...

CAD二次开发学习笔记-未完待续...总结一张关系图合并两个选择集，并改变所有对象的颜色///<summary>///合并两次选择的选择集，并将所有选择对象改变颜色///</summary>[CommandMethod("MergeSelectionSet")]publicv 查看详情

gdi+学习笔记--未完待续

生成Graphics的两种方法：l 通过事件参数Eventargs生成；l 通过控件的CreateGraphics方法生成；绘制的两种方法：l 控件的paint事件；l 重写Control类的OnPaint方法；Graphics是否需要Dispose释放资源？(也可以使用using释放资查看详情

less学习笔记(未完待续)

...法，而且连新增的特性也是使用CSS语法。这样的设计使得学习Less很轻松，而且你可以在任何时候回退到CSS（摘自官网）1.变量 Less通过@来定义变量；Less中的变量为完全的常量，所以只能被定义一次　　@base:#f938ab;　　&nbs... 查看详情

学习笔记之03做百度搜索页面，未完

<!DOCTYPEhtmlPUBLIC"-//W3C//DTDXHTML1.0Transitional//EN""http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"><htmlxmlns="http://www.w3.org/1999/xhtml"><head><metahttp-equiv=" 查看详情

后缀树组学习笔记(代码片段)

0xFF一些备注本篇博客所有证明基本略过，主要总结后缀树组的应用引用有[2009]后缀数组——处理字符串的有力工具by.罗穗骞、OIwiki、日报的大量内容实现方面本篇博客只会了倍增方法0x00一些定义第\$i\$个后缀指的是首字符在\\(... 查看详情

android学习《android开发视频教程》第二季笔记（未完待续）

视频地址：http://study.163.com/course/courseMain.htm?courseId=207001 课时22 Activity生命周期（一）1、如何在一个应用中添加新的activity第一步：添加一个activity子类（新建class，继承Activity，添加onCreate方法）右键sourse里面的override/imple... 查看详情

javaguide-rpc框架项目学习笔记-未完待续(代码片段)

本笔记为JavaGuide哥RPC项目的学习笔记，感谢Guide哥的无私奉献！RPC，RemoteProcedureCall，远程过程（方法）调用，本地上某个服务的方法要调用远程主机上某个服务的方法。RPC的原理。简单讲主要涉及三个... 查看详情

w3school之javascript学习笔记-未完待续

...（简称JS），主要用来向HTML页面添加交互行为。学习网址：http://www.w3school.com.cn/js/js_intro.asp 写入HTML输出document.write("html元素")对事件作出反应&l 查看详情

pytorch学习笔记

张量相关介绍梯度下降和方向传播pytorch实现线性回归Pytorch中常见的优化算法介绍未完待续························ 查看详情

java学习笔记：list，set，map(代码片段)

...上去。。。未完待续。。。容器也叫集合ArrayList：用数组组成的线性结构LinkedList：用链表组成的线性结构…所有的容器装的是对象，但是容器会把传进去的孤立的值自动装箱成对象，功能强大。有数组为什么要容... 查看详情

学习笔记：后缀表达式

一、中缀表达式转换为后缀表达式①扫描中缀表达式。②遇到数字将其存入后缀表达式。③遇到左括号将其入栈。④遇到右括号，出栈运算符并存入后缀表达式，直至遇到左括号，将左括号出栈结束。⑤遇到运算符，出栈运算符... 查看详情

后缀自动机学习笔记

hihocoder系列这是一个系列讲解，好康的，有六集……构建SAM并求不同子串数对应第二个讲解#include<iostream>#include<cstring>#include<cstdio>usingnamespacestd;typedeflonglongll;inttot,n,maxLen[2000005],minLen[2000005],trans[ 查看详情

后缀数组（学习心得）(代码片段)

后缀数组后缀数组是一种处理字符串的利器，很多字符串的问题都可以通过后缀数组来实现。后缀数组说简单一点就是对一个字符串的所有后缀子串进行排序。我来举个例子，比如字符串banana刚开始的时候它的后缀子串... 查看详情

后缀数组（学习心得）(代码片段)

学习笔记（ｓａｍ）

后缀自动机学习笔记性质首先，你最好认为每条边是一个字母，每个节点代表一个单词（从t0走到这个点即是此单词的一个后缀）。所有的正向边，从t0出发沿着nex形成的所有正向边构成一个DEG图，而所有的反向边，即link构成一... 查看详情

kmp算法-未完(代码片段)

...容为：next[i]表示前i个字符组成的子串的最长相同前缀和后缀的长度,要注意应用中提出的nxt[i]变化（方便在匹配两个字符串时候跳动减少时间复杂度)nxt数组模板：以i=1为起点的字符串进行处理voidget_nxt()nxt[0]=nxt[1]=0;for(inti=2,j=0;i&l... 查看详情

学习笔记第十八节课

...不压缩小很多，机房里的带宽很贵。（节省资源）Linux里后缀名虽然可以随便写，但是也要根据后缀名去分别文件是干嘛的。为了方便区分，后缀名要写成这些后缀，压缩工具也会自动生成类似的后缀名。gzip压缩工具直接跟文件... 查看详情