简述网站开发的三层架构,推广网站的方法有哪些,关键词首页排名优化价格,动态表单的设计与实现子串#xff1a;从原串中选取连续的一段#xff0c;即子串 空串也是子串 后缀#xff1a;suf(k)为s(k…n)构成的子串 任何子串都是某个后缀的前缀 最长公共前缀 lcp(suf(i),suf(j))
问题#xff1a;
将所有后缀suf(1),suf(2),suf(N)按照字典序从小到大排序
暴力sort N2 …子串从原串中选取连续的一段即子串 空串也是子串 后缀suf(k)为s(k…n)构成的子串 任何子串都是某个后缀的前缀 最长公共前缀 lcp(suf(i),suf(j))
问题
将所有后缀suf(1),suf(2),suf(N)按照字典序从小到大排序
暴力sort N2 logN 二分hash : Nlog2N cmp函数中二分suf(i)和suf(j)的lcp return s[i|lcp|] s[j|lcp|] ------- 以上为暴力做法 进入正文 SA[1]排序第1的后缀的开始位置 Rank[i]后缀suf(i)的排名 Rank[sa[l]] l sa[Rank[i]] i 求sa然后得到rank 倍增 sub[i][k]s从i开始长度为 2k的子串 sub[i][k] s[i…i(1k)-1 ],超过N的部分都视为’\0’(字典序最小符号) rank[i][k]sub[i][k]在长度2k的所有子串中的排名 sa[1][k] :在长度2k的所有子串中排名第1的子串的开始位置 step 1先求sub[1][0],sub[2][0],…,sub[N][0]的字典排序 先求长度为1的子串然后看字典序是多少 再求2,48N 当子串长度2kN时子串排序就是后缀排序 利用rank[i…N][k],如何求出rank[1…N][k1] 二分比较 对于两个子串sub[i][k1]与sub[j][k1]比较 先比较rank[i][k]与rank[j] [ k ] (先比前半部分) 如果相等再比较rank[i2k]与rank [ j2k ] (比较后半部分) 相当于二元组第一关键字–rank[i][k],第二–rank[i2k][k]排序 注意rank[i][k]值域是不超过N的正整数可以用基数排序桶排序 基础排序先按second再按照first 复杂度O(Nd) d是最大位数此处d是2因为两个关键词 写SA时用cnt数组实现 将a[i]数组1~N基数排序结果存放在sa数组中 sa[1]排名第1th的数在a中的下标
for(int i1;iN;i)cnt[a[i];//桶排
for(int i1;iN;i)cnt[i]cnt[i-1];//求前缀和
for(int iN;i;i--)sa[cnt[a[i]]--]i;//sa[cnt[a[i]]]i,cnt[a[i]]--;a[2,1,2,4,2] cnt[1,3,0,1,0] cnt[1,4,4,5,5] 大致过程 for k 1 ~ logN 按rank[i2k][k]基数排序(第二关键字) 按照rank[i][k]基数排序第一关键字 得到sa[i][k1]数组 由sa[i][k1]求出rank[i][k1] 动画链接 数据结构和算法动态可视化 (Chinese) sa—rank rk[i]中有并列
for(p0;i1;in;i)
{if(oldrk[sa[i]]oldrk[sa[i-1]]oldrk[sa[i]k]oldrk[sa[i-1]k])rk[sa[i]]p;else rk[sa[i]]p;
}oi-wiki
代码
#include algorithm
#include cstdio
#include cstring
#include iostreamusing namespace std;const int N 1000010;char s[N];
int n, sa[N], rk[N 1], oldrk[N 1], id[N], cnt[N];int main() {int i, m, p, w;scanf(%s, s 1);n strlen(s 1);m max(n, 300);for (i 1; i n; i) cnt[rk[i] s[i]];for (i 1; i m; i) cnt[i] cnt[i - 1];for (i n; i 1; --i) sa[cnt[rk[i]]--] i;//基数排序for (w 1; w n; w 1) {//倍增memset(cnt, 0, sizeof(cnt));for (i 1; i n; i) id[i] sa[i];for (i 1; i n; i) cnt[rk[id[i] w]];for (i 1; i m; i) cnt[i] cnt[i - 1];for (i n; i 1; --i) sa[cnt[rk[id[i] w]]--] id[i];//上面为第二部分基数排序下面为第二部分基数排序memset(cnt, 0, sizeof(cnt));for (i 1; i n; i) id[i] sa[i];for (i 1; i n; i) cnt[rk[id[i]]];for (i 1; i m; i) cnt[i] cnt[i - 1];for (i n; i 1; --i) sa[cnt[rk[id[i]]]--] id[i];memcpy(oldrk, rk, sizeof(rk));for (p 0, i 1; i n; i) {if (oldrk[sa[i]] oldrk[sa[i - 1]] oldrk[sa[i] w] oldrk[sa[i - 1] w]) {rk[sa[i]] p;} else {rk[sa[i]] p;}//由sa得到新的rank数组}}for (i 1; i n; i) printf(%d , sa[i]);return 0;
}这个代码会超时经过优化后
#include algorithm
#include cstdio
#include cstring
#include iostreamusing namespace std;const int N 1000010;char s[N];
int n, sa[N], rk[N], oldrk[N 1], id[N], px[N], cnt[N];
// px[i] rk[id[i]]用于排序的数组所以叫 pxbool cmp(int x, int y, int w) {return oldrk[x] oldrk[y] oldrk[x w] oldrk[y w];
}int main() {int i, m 300, p, w;scanf(%s, s 1);n strlen(s 1);for (i 1; i n; i) cnt[rk[i] s[i]];for (i 1; i m; i) cnt[i] cnt[i - 1];for (i n; i 1; --i) sa[cnt[rk[i]]--] i;for (w 1; w n; w 1, m p) { // mp 就是优化计数排序值域for (p 0, i n; i n - w; --i) id[p] i;for (i 1; i n; i)if (sa[i] w) id[p] sa[i] - w;memset(cnt, 0, sizeof(cnt));for (i 1; i n; i) cnt[px[i] rk[id[i]]];for (i 1; i m; i) cnt[i] cnt[i - 1];for (i n; i 1; --i) sa[cnt[px[i]]--] id[i];memcpy(oldrk, rk, sizeof(rk));for (p 0, i 1; i n; i)rk[sa[i]] cmp(sa[i], sa[i - 1], w) ? p : p;}for (i 1; i n; i) printf(%d , sa[i]);return 0;
}要求全文背诵 复杂度为O(n logn)
