信息
- 拼 音
- hou zhui shu zu
- 子 串
- 字符串 S 的子串
- 中文名
- 后缀数组
- 外文名
- Suffix Array
后缀数组基本定义
字符串 S 的子串 r[i,j] , i ≤ j ,表示 r 串中从 i 到 j 这一段,就是顺次排列 r[i],r[i+1],...,r[j] 形成的字符串。后缀是指从某个位置 i 开始到整个串末尾结束的一个特殊子串。字符串 r 的从 第 i 个字符开始的后缀表示为 Suffix(i) ,也就是Suffix(i)=r[i,len(r)] 。大小比较:关于字符串的大小比较,是指通常所说的“字典顺序”比较,也就是对于两个字符串u、v,令i 从1 开始顺次比较u[i]和v[i],如果u[i]=v[i]则令 i 加1,否则若u[i]v[i]则认为u>v(也就是vlen(u)或者i>len(v)仍比较不出结果,那么若len(u)len(v)则u>v。从字符串的大小比较的定义来看,S 的两个开头位置不同的后缀u 和v 进行比较的结果不可能是相等,因为u=v 的必要条件len(u)=len(v)在这里不可能满足。后缀数组 SA 是一个一维数组,它保存从 1 到 n 的某个排列 SA[1 ] ,SA[2] , …… , SA[n] ,并且保证suffix(SA[i]) < Suffix(SA[i+1]) , 1 ≤ i
-
后缀数组
2019-01-30 19:41:24后缀数组模板+POJ3581 后缀数组指的是将某个字符串的所有后缀按字典序排序后得到的数组,基本概念可参考后缀数组。 下面为后缀数组的模板 import java.util.Scanner; public class Main { static int[] sa;//后缀...后缀数组模板+POJ3581
后缀数组指的是将某个字符串的所有后缀按字典序排序后得到的数组,基本概念可参考后缀数组。
下面为后缀数组的模板
import java.util.Scanner; public class Main { static int[] sa;//后缀数组suffix array static int[] cnt;//计数数组 static int[] x; static int[] y; static String str; static int length; public static void main(String[] args) { Scanner in = new Scanner(System.in); //输入一个字符串 str = in.next(); sa = new int[500]; cnt = new int[500]; x = new int[500]; y = new int[500]; sa(); for(int i = 0;i < length;i++) { System.out.println(i + " " + sa[i] + " " + str.substring(sa[i])); } } public static void sa() { length = str.length(); int m = 127;//通过ASCII码方式确定字符串范围 /* 在倍增之前先进行一次基数排序 * x[i]储存str里每一个字符的ASCII码 */ for(int i = 0;i < m;i++) cnt[i] = 0;//开始所有都为0 for(int i = 0;i < length;i++) cnt[x[i] = str.charAt(i)]++;//通过将字符转换成ASCII码方式对str里面所有字符进行计数 for(int i = 1;i < m;i++) cnt[i] += cnt[i-1];//从小到大进行编号,为排序做准备。如 str = "aaabba", cnt[a] = 4; cnt[b] = 6; 这时str可被编号为 1 2 3 5 6 4 for(int i = length-1;i >= 0;i--) sa[--cnt[x[i]]] = i;//sa[i] = j 表示的含义是从小到大排名为i的后缀下标为j,rank数组刚好与sa相反,rank[i] = j表示后缀下标为i的排名为j //上行表示的便是对sa数组的求解,这时可用到上一行编号的结果,假如编号已经为 1 2 3 5 6 4,根据排名和下标可得sa数组为 1(编号为1的下标为1,以此类推) 2 3 6 4 5 for(int k = 1;k <= length; k <<= 1) {//倍增 //对第二关键字进行排序 int p = 0; for(int i = length - 1;i >= length - k;i--) y[p++] = i;//相当于补零,由于补的0肯定是最小,因此顺序是最前的 for(int i = 0;i < length;i++) { if(sa[i] >= k) { y[p++] = sa[i] - k; } } //例如要排序的数是:92,81,30,24,57,96; //对第二关键字排序得到的结果为 y[] = 3,2,1,4,6,5 //x[y[]] = 30,81,92,24,96,57 表示结果位置上的数 //再一次基数排序,对第一关键字进行排序 for(int i = 0;i < m;i++) cnt[i] = 0; for(int i = 0;i < length;i++) cnt[x[y[i]]]++; for(int i = 1;i < m;i++) cnt[i] += cnt[i-1]; for(int i = length - 1;i >= 0;i--) sa[--cnt[x[y[i]]]] = y[i]; swap();//x和y进行交换 p = 1; x[sa[0]] = 0; for(int i = 1;i < length;i++) { if(y[sa[i-1]] == y[sa[i]] && y[sa[i-1]+k] == y[sa[i] + k]) x[sa[i]] = p-1; else x[sa[i]] = p++; } if(p >= length) {//当每一个元素都是不同的排名的时候,可以结束循环 break; } m = p; } } public static void swap() { int[] tmp = new int[500]; tmp = x; x = y; y = tmp; } }
POJ3581:题意为给N个数字序列A1到An,其中A1比其他的数字都大,要将该数字序列分为三段,并将每段分别反转,求得到字典序最小的序列,N <= 200000。
如 N = 5; 序列A = { 10,1,2,3,4 }。
得到结果为 1,10,2,3,4 (分为 {10,1} {2} {3,4} 三段,然后反转)
通过离散化和后缀数组模板完成import java.util.Arrays; import java.util.Scanner; public class Main{ static int[] sa; static int[] cnt; static int[] x; static int[] y; static int length; static int num; static int[] array; static final int maxn = 200050; static int[] res; static int[] ori; static node[] n; public static void main(String[] args) { Scanner in = new Scanner(System.in); num = in.nextInt(); n = new node[num]; array = new int[num]; res = new int[num]; ori = new int[num]; for(int i = num-1;i >= 0;i--) { n[i] = new node(); n[i].number = in.nextInt(); n[i].id = i; } Arrays.sort(n); for(int i = 0; i< num; i++){ if(i != 0 && n[i].number == n[i-1].number) { array[n[i].id] = array[n[i-1].id]; continue; } array[n[i].id] = i+1; } ori = array; sa = new int[maxn]; cnt = new int[maxn]; x = new int[maxn]; y = new int[maxn]; sa(); /* for(int i = 0;i < length;i++) { System.out.print(i + " " + sa[i] + " "); for(int j = sa[i];j < num;j++) { System.out.print(array[j]); } System.out.println(); } */ int p1 = -1; for(int i = 0;i < num;i++) { p1 = num - sa[i]; if(p1 >= 1 && num - p1 >= 2) break; } //System.out.println(p1); int count = 0; for(int i = num-p1;i < num;i++) { res[count] = n[ori[i] - 1].number; count++; } int[] t = new int[(num-p1)*2]; for(int i = 0;i <= 1;i++) { for(int j = 0;j < num-p1;j++) { t[i*(num-p1) + j] = array[j]; } } array = t; /* for(int i = 0;i < 8;i++) { System.out.println(array[i]); }*/ sa(); /* for(int i = 0;i < length;i++) { System.out.print(i + " " + sa[i] + " "); for(int j = sa[i];j < array.length;j++) { System.out.print(array[j]); } System.out.println(); } */ int p2 = -1; for(int i = 0;i < 2 * (num - p1);i++) { p2 = num - sa[i]; if(p2 - p1 >= 1 && num - p2 >= 1 && sa[i] > 0 && sa[i] < num - p1) { break; } } //System.out.println(p2); for(int i = num - p2;i < num - p1;i++) { res[count] = n[ori[i] - 1].number; count++; } for(int i = 0;i < num - p2;i++) { res[count] = n[ori[i] - 1].number; count++; } for(int i = 0;i < num;i++) { System.out.println(res[i]); } } public static void sa() { length = array.length; int m = maxn; for(int i = 0;i < m;i++) cnt[i] = 0; for(int i = 0;i < length;i++) cnt[x[i] = array[i]]++; for(int i = 1;i < m;i++) cnt[i] += cnt[i-1]; for(int i = length-1;i >= 0;i--) sa[--cnt[x[i]]] = i; for(int k = 1;k <= length; k <<= 1) { int p = 0; for(int i = length - 1;i >= length - k;i--) y[p++] = i; for(int i = 0;i < length;i++) { if(sa[i] >= k) { y[p++] = sa[i] - k; } } for(int i = 0;i < m;i++) cnt[i] = 0; for(int i = 0;i < length;i++) cnt[x[y[i]]]++; for(int i = 1;i < m;i++) cnt[i] += cnt[i-1]; for(int i = length - 1;i >= 0;i--) sa[--cnt[x[y[i]]]] = y[i]; swap(); p = 1; x[sa[0]] = 0; for(int i = 1;i < length;i++) { if(y[sa[i-1]] == y[sa[i]] && y[sa[i-1]+k] == y[sa[i] + k]) x[sa[i]] = p-1; else x[sa[i]] = p++; } if(p >= length) { break; } m = p; } } public static void swap() { int[] tmp = new int[maxn]; tmp = x; x = y; y = tmp; } } class node implements Comparable{ int id; int number; @Override public int compareTo(Object o) { node t = (node)o; if(this.number > t.number) { return 1; }else if(this.number == t.number) { if(this.id > t.id) { return 1; }else { return -1; } }else { return -1; } } }
收藏数
14,321
精华内容
5,728