构造后缀数组
倍增前缀法
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 |
#define SUFFIX_ARRAY_PFXDBL #ifdef SUFFIX_ARRAY_PFXDBL namespace SA{ /* Suffix Array, Prefix Doubling Method <SUBSCRIPT_START_FROM,SIZE> MAXN : Maximum length for string s : String for building suffix array <0,MAXN> t,t2,c : [Auxiliary] buffers <0,MAXN> n : Length of string sa : Suffix Array, Lexicographically ith suffix starts from. <0,MAXN> rank : Suffix Rank, rank of the suffix starts from i <0,MAXN> height : LCP of suffix starts from sa[i] and sa[i-1] <1,MAXN> build_sa(int m) : m is the size of character set("character" being 0~m-1), should set s and n previously. getHeight() : Calculate height and rank array accordingly. #define REP(i,t) for(int i = 0;i < t; i++) #define REP_R(i,t) for(int i = t-1;i >= 0; i--) #define REP_1(i,t) for(int i = 1;i <= t; i++) #define REP_1R(i,t) for(int i = t;i >= 1; i--) Time : O(nlogn) Space : 7n */ const int MAXN = 10005; char s[MAXN]; int sa[MAXN],t[MAXN],t2[MAXN],c[MAXN],rank[MAXN],height[MAXN],n; void build_sa(int m){ int *x = t,*y = t2; //第一次基数排序 REP(i, m) c[i] = 0; //重置排序数组 REP(i, n) c[x[i]=s[i]]++; //拷贝字符串内容到x缓冲区，并在基数排序数组中统计字符数量 REP_1(i, m-1) c[i] += c[i-1]; //基数排序数组求前缀和以算出排名 REP_R(i, n-1) sa[--c[x[i]]] = i; //从后往前顺次查询后缀的排名写入SA(字符相同的时候，长度小的靠前，长度大的靠后) //此时的x数组可以看成是保存了各个位置开始的后缀对应的第一基准 for(int k = 1;k <= n; k <<= 1){ //第k次基数排序,单组长度2^k int p = 0; //利用SA排序第二基准，y存储的是第二基准排序之后的后缀开始位置 for(int i = n-k;i < n; i++) y[p++] = i; //长度没达到k，这种只能看第一基准，第二基准视为0 REP(i, n) if(sa[i] >= k) y[p++] = sa[i]-k; //从前往后扫SA，即从字典序小的后缀开始扫，如果这个后缀的开始位置>=k的话，这个后缀在sa中的结果实际上是i-k的第二基准 //排序第一基准 REP(i, m) c[i] = 0; //重置排序数组 REP(i, n) c[x[y[i]]]++; //按第二基准顺序读取第一基准进行统计 REP(i, m) c[i] += c[i-1];//基数排序数组求前缀和以算出排名 REP_R(i, n-1) sa[--c[x[y[i]]]] = y[i];//按第二基准从后往前顺次查询后缀的排名写入SA //准备下一次排序的第一基准序列x //第二基准排序结果y没有用了，上一次的第一基准序列x还有用，直接互换 swap(x, y); //现在y是上一次的第一基准序列 p = 1; x[sa[0]] = 0;//第一基准从0开始 //现在的sa是排好序的，从小到大查询，如果两项无法分出先后，就令成统一基准，否则基准自增 REP_1(i, n-1) x[sa[i]] = ((y[sa[i-1]] == y[sa[i]]) && (y[sa[i-1]+k]==y[sa[i]+k]))? p-1 : p++; if(p >= n) break; //如果基准数已达n，说明排序完成，所有后缀已经分出先后 m = p; //下一轮排序的基准数是p } } void getHeight(){ int i,j,k = 0; REP(i, n) rank[sa[i]] = i; for(i = 0;i < n; height[rank[i++]] = k) for(k?k--:0,j = sa[rank[i]-1];s[i+k]==s[j+k];k++); return; } } #endif |
DC3
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 |
#define SUFFIX_ARRAY_DC3 #ifdef SUFFIX_ARRAY_DC3 namespace SA{ /* Suffix Array, DC3 Method <SUBSCRIPT_START_FROM,SIZE> MAXN : Maximum length of string wa,wb : [Auxiliary] buffer <0,MAXN> wv,ws : [Auxiliary] buffer <0,MAXN> rank : Suffix Rank, rank of the suffix starts from i <0,MAXN> height : LCP of suffix starts from sa[i] and sa[i-1] <1,MAXN> sort() : [Auxiliary] Radix sort c0() : [Auxiliary] Checker for same rank character tuple c12() : [Auxiliary] Comparer in the merging process F() : [Auxiliary] Find suffix(x)'s new position G() : [Auxiliary] Find suffix(x)'s original position dc3(r,sa,n,m) : Build Suffix Array using DC3 method : r : String used to build Suffix Array <0,MAXN*3> sa : Suffix Array, Lexicographically ith suffix starts from. <0,MAXN*3> n : String length m : Character set size ATTENTION : characters in string r should be 1~m and r should be ended with 0. getHeight(r,sa,n) : Get rank and height arrary for given string r and corrsponding Suffix Array sa. #define REP(i,t) for(int i = 0;i < t; i++) #define REP_R(i,t) for(int i = t-1;i >= 0; i--) #define REP_1(i,t) for(int i = 1;i <= t; i++) #define REP_1R(i,t) for(int i = t;i >= 1; i--) Time : O(n) Space : 12n */ const int MAXN = 10005; int wa[MAXN],wb[MAXN],wv[MAXN],ws[MAXN]; inline int c0(int *r,int a,int b){ return r[a]==r[b]&&r[a+1]==r[b+1]&&r[a+2]==r[b+2]; } inline int c12(int k,int *r,int a,int b){ if(k==2) return r[a] < r[b] || (r[a] == r[b] && c12(1,r,a+1,b+1)); else return r[a] < r[b] || (r[a] == r[b] && wv[a+1] < wv[b+1]); } void sort(int *r,int *a,int *b,int n,int m){ /* 基数排序,b是a中的位置按对应的r中字符大小排序之后的结果 r : 字符串 a : 要排序的项目在字符串上的位置 b : 排序的结果要存储到的数组 n : 要排序的项目总数 m : 字符集大小 */ REP(i, n) wv[i] = r[a[i]];//从字符串中抽出要排序的项目到wv REP(i, m) ws[i] = 0;//重置基数排序数组 REP(i, n) ws[wv[i]]++;//统计各种字符的数量 REP_1(i, m-1) ws[i] += ws[i-1];//计算基数排序数组的前缀和以确定排名 REP_R(i, n-1) b[--ws[wv[i]]] = a[i];//把排序结果写入b数组 } inline int F(const int x,const int tb){ return x/3 + ((x%3==1)?0:tb); } inline int G(const int x,const int tb){ return (x<tb)?(x*3+1):((x-tb)*3+2); } void dc3(int *r,int *sa,int n,int m){ /* rn : 要递归处理的新字符串 san : 新字符串对应的后缀数组 ta : 起始位置模3为0的后缀总数 tb : 起始位置模3为1的后缀总数 tbc : 起始位置模3为1或2的后缀总数 */ int *rn = r+n, *san = sa+n, ta = 0, tb = (n+1)/3, tbc = 0, p; //PART1: 计算好起始位置模3不等于0的后缀的对应的SA //用基数排序把3个字符合并成一个字符 r[n] = r[n+1] = 0; REP(i, n) if(i%3) wa[tbc++] = i;//记录起始位置模3不为0的后缀到wa中 sort(r+2, wa, wb, tbc, m);//以第三个字符为基准排序 sort(r+1, wb, wa, tbc, m);//在三准基础上以第二个字符为基准排序 sort(r, wa, wb, tbc, m);//在二三准基础上以第一个字符为基准排序 //这样就完成了三个字符的合并 //根据排序结果求新的字符串 //F(x) : 计算原字符串起始位置是x的后缀在新字符串中的起始位置 //c0() : 判定两个字符组是否完全一致 int i,j; for(p = 1,rn[F(wb[0],tb)] = 0,i = 1;i < tbc; i++) rn[F(wb[i],tb)] = c0(r, wb[i-1], wb[i])? (p-1):(p++); if(p < tbc) //递归处理新字符串(有些字符组无法区分) dc3(rn, san, tbc, p); else //可以直接求出san的情形(所有的字符组可以区分) REP(i, tbc) san[rn[i]] = i; //PART2: 计算好起始位置模3等于0的后缀对应的SA //第二基准的排序结果可以藉由san直接得到 REP(i, tbc) if(san[i] < tb) wb[++ta] = san[i]*3; if(n%3 == 1) wb[ta++] = n-1;//san中没有n-1，所以要特殊处理 sort(r, wb, wa, ta, m);//第一基准为新加的字符，在算好的第二基准基础上排序 //把san中的结果做一个反射，因为我们接下来要查询在新字符串中的以x结尾的后缀的排名是多少 //G(x): 计算新字符串中起始位置为x的后缀在原字符串中的位置 REP(i, tbc) wv[wb[i] = G(san[i],tb)] = i; //PART3: 合并前面两部分的结果 //c12(): 合并时使用的比较 for(i = j = p = 0;i < ta && j < tbc; p++) sa[p] = c12(wb[j]%3, r, wa[i], wb[j])?wa[i++] : wb[j++]; for(;i < ta; p++) sa[p] = wa[i++]; for(;j < tbc; p++) sa[p] = wb[j++]; } int rank[MAXN],height[MAXN]; void getHeight(int *r,int *sa,int n){ int i,j,k = 0; REP(i, n) rank[sa[i]] = i; for(i = 0;i < n; height[rank[i++]] = k) for(k?k--:0,j = sa[rank[i]-1];r[i+k]==r[j+k];k++); return; } } #endif |
经典问题
最长公共前缀(LCP)
可重叠最长重复子串
不可重叠最长重复子串
可重叠k次重复最长子串
不相同子串数目
最长回文子串
最长循环节
重复次数最多的循环节
最长公共子串
长度不小于k的公共子串个数
在至少k个字符串中出现的最长子串
每个字符串至少出现两次且不重叠的最长子串
出现或反转后出现在每个字符串中的最长子串
