app电商网站,新闻门户网站建设方案,移动惠生活app下载网址,如何解析域名后缀数组感觉有点不好解释#xff0c;简单记录一下板子。
后缀数组性质
lcp(i, j):指的是第i个后缀以及第j个后缀的最大公共前缀的长度 lcp(i, j) lcp(j, i) lcp(i, i) len(i) lcp(i, j) min(lcp(i, k), lcp(k, j))
在o(nlogn)的时间复杂度内处理一个字符串#xff…后缀数组感觉有点不好解释简单记录一下板子。
后缀数组性质
lcp(i, j):指的是第i个后缀以及第j个后缀的最大公共前缀的长度 lcp(i, j) lcp(j, i) lcp(i, i) len(i) lcp(i, j) min(lcp(i, k), lcp(k, j))
在o(nlogn)的时间复杂度内处理一个字符串得到三个数组。
sa[i]表示排名为i的后缀是字符串中第几个后缀。
rk[i]表示字符串中第几个后缀的排名。
height[i]sa[i] 与 sa[i - 1] 的后缀的最长公共前缀的长度。
int n, m;
int o[N];
int c[N], x[N], y[N], sa[N], rk[N], height[N];
char s[N];
// x最开始表示每个字符离散化后的值也就是Ascll码第一关键值
void get_sa() {for(int i 1; i n; i ) c[x[i] s[i]] ; for(int i 2; i m; i ) c[i] c[i - 1];for(int i n; i; i --) sa[c[x[i]] --] i; // 以上是得到按照第一个字符进行排序后的后缀顺序sa以及x数组也就是每个后缀的第一关键字 for(int k 1; k n; k 1) { int num 0;for(int i n - k 1; i n; i ) y[ num] i; // 没有第二关键字就是最小的直接排序就行 for(int i 1; i n; i ) if(sa[i] k) // 当前大小排名为i的后缀存在第二关键字 y[ num] sa[i] - k; // 减k之后才是以当前为第二关键字的后缀// 以上是按照第二关键字进行排序得到排序后的后缀顺序y for(int i 1; i m; i ) c[i] 0;for(int i 1; i n; i ) c[x[i]] ; for(int i 2; i m; i ) c[i] c[i - 1];for(int i n; i; i --) sa[c[x[y[i]]] -- ] y[i], y[i] 0; // 以上是按照第一关键字进行排序之后的后缀顺序sa// 当前的操作已经完成需要更新一下第一关键字因为对于下一次循环的排序来说第一关键字是当前的第一关键字和第二关键字的整体所以需要对这个整体进行离散得到新的x数组第一关键字 swap(x, y); // y已经没用了直接用来存储之前的第一关键字进行使用x[sa[1]] 1, num 1; // 第一个位置for(int i 2; i n; i ) x[sa[i]] (y[sa[i]] y[sa[i - 1]] y[sa[i] k] y[sa[i - 1] k]) ? num : num; // 如果第一关键字和第二关键字都相同则num值等于上一个位置否则加一因为当前的sa顺序已经是排序之后的只需要考虑相等值得离散值相同即可。if(num n) break; // 排序完成m num;// 更新一下值域范围一个小的时间优化}
} void get_height() {for(int i 1; i n; i ) rk[sa[i]] i;for(int i 1, k 0; i n; i ) {if(rk[i] 1) continue;if(k) k --; int j sa[rk[i] - 1];while(i k n j k n s[i k] s[j k]) k ;height[rk[i]] k;}
}inline void sovle() {cin s 1;n strlen(s 1), m 122;get_sa();get_height();for(int i 1; i n; i ) cout sa[i] ;cout endl;for(int i 1; i n; i ) cout rk[i] ;cout endl;for(int i 1; i n; i ) cout height[i] ;cout endl;
}
