这章要比上章的AC自动机要难理解。
这里首先要理解基数排序：基数排序与桶排序，计数排序【详解】
下面通过这个积累信心：五分钟搞懂后缀数组！后缀数组解析以及应用(附详解代码)
下面认真研读下这篇： [转载]后缀数组算法总结 里面的图片真Nice
然后找到适合再加深认识的：后缀数组学习笔记 算法合集之《后缀数组——处理字符串的有力工具》
后缀数组：通过对字符串后缀的处理得到子串的信息。
这里我通过借鉴上面的blog和训练指南写下了一段学习程序，还有在线多模板匹配的二分查找未完成。
用代码和测试数据的结果对比第三篇文章里的图片，有助于理解后缀数组sa的构建过程。
1 #include <bits/stdc++.h> 2 using namespace std; 3 const int maxn = 1010; 4 char s[maxn]; //字符串s，每个字符值[0,m-1] 5 int c[maxn]; //辅助数组 6 int x[maxn]; //rank数组，下标表示关键字的位置，值表示关键字的名次 7 // x代表每个后缀的前缀的种类 8 int y[maxn]; //表示排序后的第二关键字数组，下标表示名次 9 //值表示第二关键字的首字符位置 10 int sa[maxn]; 11 /* 在构造完前表示关键字数组：下标表示名次，值表示关键字首字符位置，值相同时名次根据在原串中的相对位置决定 12 * 构造完成后表示后缀数组，下标表示名次，值表示后缀的首字符位置 13 */ 14 void show_sort_to_get_first_sa(int n){ 15 cout << "第一次计数排序结果:" << endl; 16 for(int i=0; i<n; i++){ 17 cout << "第" << i << "位" << endl; 18 cout << "大小 = " << x[i] << " " << char(x[i]) << endl; 19 cout << "该后缀的首字符的下标(或称后缀-)： " << sa[i] << endl; 20 // aaaaaabb 21 // 01345627 22 } 23 } 24 void show_second_key(int n){ 25 cout << "y的结果" << endl; 26 for(int i=0; i<n; i++){ 27 cout << y[i] << " "; 28 }cout << endl; 29 /* 30 * xaaaaabb 31 * 70234516 32 */ 33 } 34 void show_last(int n){ 35 cout << " sa的终值: "; 36 for(int i=0; i<n; i++){ 37 cout << sa[i] << " "; 38 }cout << endl; 39 } 40 bool cmp(int *f, int x, int y, int k){ 41 return f[x]==f[y] && f[x+k]==f[y+k]; 42 } 43 void build_sa(int m, int n){ 44 //每个字符值为[0,m-1] 45 //字符串长度为n 46 for(int i=0; i<=m; i++){ 47 c[i] = 0; 48 } 49 for(int i=0; i<n; i++){ 50 c[x[i] = s[i]]++; 51 } //x是s中字符的键值//c存储各键值在输入数组中出现的次数 52 for(int i=1; i<m; i++){ 53 c[i] += c[i-1]; 54 } 55 /* 56 * 计算前缀和，即可知小于小于每个数的个数 57 * aabaaaab=11211112 --> c[1]=6, c[2]=2 58 * 计算前缀和--> c[2]=8 59 */ 60 for(int i=n-1; i>=0; i--){ 61 sa[--c[ x[i]]] = i; 62 }//满足第一关键字的同时满足第二关键字 63 /* 以上代码 64 * 对后缀的第一位进行计数排序。 65 */ 66 show_sort_to_get_first_sa(n); 67 68 69 for(int k=1; k<=n; k<<=1){ 70 // k:当前子字符串长度 71 int p = 0; 72 //当前的第二关键字可直接由上次的sa得到 73 for(int i=n-k; i<n; i++){ 74 y[p++] = i; 75 }// 长度越界，第二关键字为0 76 for(int i=0; i<n; i++){ 77 if(sa[i] >= k){ 78 y[p++] = sa[i] - k; //-k后移上次排序的结果 79 //y存储对第二关键字排序的结果 80 } 81 }//使用有第k个字符的字符串，直接排序第二关键字 82 //以上结合两个关键字进行总排序 83 84 show_second_key(n); 85 86 //基数排序第一关键字 87 for(int i=0; i<=m; i++){ 88 c[i] = 0; 89 } 90 for(int i=0; i<n; i++){ 91 c[x[y[i]]]++; 92 } 93 for(int i=1; i<m; i++){ 94 c[i] += c[i-1]; 95 } 96 for(int i=n-1; i>=0; i--){ 97 sa[ --c[ x[ y[i]]]] = y[i]; 98 //y[i] = 0; 99 } //更新sa， 100 swap(x, y); //用y暂存上一轮的x(rank) 101 /* 102 * 集和两个关键字排总序 103 * 完成了关键字的合并 104 */ 105 p = 1; x[sa[0]] = 0; 106 //用已经完成的sa来更新与它互逆的rank(x) 107 for(int i=1; i<n; i++){ 108 x[sa[i]] = cmp(y,sa[i],sa[i-1],k)?p-1:p++; 109 } 110 if(p >= n) break; //即使倍增，sa也不会改变 111 m = p; 112 } 113 114 show_last(n); // 115 116 } 117 int rank[maxn]; //rank[string's num] = rank 118 int height[maxn]; //height[rank] = len of lcp 119 void getheight(int n){ 120 for(int i=0; i<n; i++){ 121 rank[sa[i]] = i; 122 }//计算每个字符串字典序的排名 123 /* 124 * h[i]:第i个位置开始的后缀与排名在其前一名的后缀的最长公共前缀 125 * k=0:从首字符开始看第i个字符串和第j个字符串前面有多少是相同的 126 * k!=0， height[rank[i]] = height[rank[i-1]] - 1,LCP长度最少是k-1, 127 * 于是从首字符后面k-1个字符开始检查 128 */ 129 for(int i=0, k=0; i<n; i++){ 130 if(k) k--; 131 /* 若k不为0, h[i]>=h[i-1]-1，最长公共前缀长度至少是k-1，从首字符后k-1开始检查 132 * h[i-1]-1是一系列h值的最小值，包括后缀i和排在它前一个的后缀p的LCP长度 133 */ 134 int j = sa[rank[i] - 1]; 135 while(j+k<n && i+k<n && s[j+k]==s[i+k]) k++; 136 //计算height[rank[i]]，LCP(rank[i],rank[i]-1) 137 height[rank[i]] = k; 138 } 139 } 140 int main(){ 141 freopen("in.txt", "r", stdin); 142 int n, m; 143 cin >> n >> m; 144 cin >> s; 145 build_sa(m, n); 146 for(int i=0; i<n; i++){ 147 for(int j=sa[i]; j<n; j++){ 148 cout << s[j] << " "; 149 }cout << endl; 150 } 151 getheight(n); 152 return 0; 153 } 154 /* 155 in.txt 156 8 200 157 aabaaaab 158 */
还没开始做题，这个知识点怕暂时要凉了。