AcWing 140. 后缀数组(Java)
原题链接
中等
作者:
上杉
,
2021-05-10 13:32:38
,
所有人可见
,
阅读 351
import java.io.*;
import java.util.Arrays;
import java.util.Comparator;
/**
* @program: 算法题
* @author: 上杉
* @create: 2021-05-10 13:04
**/
public class Main {
static String str;
static int len;
static Integer[] sa;
static long[] sum;
static long[] p;
static int P = 131;
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
str = bf.readLine();
len = str.length();
sa = new Integer[len + 1];
sum = new long[len + 1];
p = new long[len + 1];
for (int i = 1; i <= len; i++) sa[i] = i;
p[0] = 1;
for (int i = 1; i <= len; i++) {
sum[i] = sum[i-1] * P + str.charAt(i-1) - 'a' + 1;
p[i] = p[i-1] * P;
}
// System.out.println(getMaxPrefix(sa[5], sa[10]));
Arrays.sort(sa,1,len + 1,new Comparator<Integer>(){
@Override
public int compare(Integer o1, Integer o2) {
int max = getMaxPrefix(o1, o2);
int n1 = o1 + max > len ? Integer.MIN_VALUE : str.charAt(o1 - 1 + max);
int n2 = o2 + max > len ? Integer.MIN_VALUE : str.charAt(o2 - 1 + max);
return n1 <= n2 ? -1 : 1;
}
});
for (int i = 1; i <= len ; i++) {
bw.write(sa[i] - 1+" ");
}
bw.write("\n");
for (int i = 1; i <= len ; i++) {
if (i == 1){
bw.write("0 ");
}else {
int maxPrefix = getMaxPrefix(sa[i - 1], sa[i]);
bw.write(maxPrefix+" ");
}
}
bw.flush();
}
private static int getMaxPrefix(Integer o1, Integer o2) {
int l = 0;
int r = Math.min(len - o1 + 1,len - o2 + 1) + 1;
while (l < r){
int mid = (l + r) >> 1;
//o1,o1+mid-1
long hash1 = sum[o1+mid-1] - sum[o1 - 1] * p[mid];
long hash2 = sum[o2+mid-1] - sum[o2 - 1] * p[mid];
if (hash1 == hash2){
l = mid + 1;
}else {
r = mid;
}
}
return r - 1;
}
}