# 挑战程序竞赛系列（71）：4.7高度数组（1）

## 挑战程序竞赛系列（71）：4.7高度数组（1）

LCP概念：在后缀数组中相邻两个后缀的最长公共前缀（Longest Common Prefix）

```import java.io.IOException;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class Main{

String INPUT = "./data/judge/201709/P2217.txt";

static Scanner in;
public static void main(String[] args) throws IOException {
in = new Scanner(System.in);
new Main().run();
}

int t = in.nextInt();
in.nextLine();
while (t --> 0) {
String S = in.nextLine();
String T = in.nextLine();
StringBuilder sb = new StringBuilder();
sb.append(S + '\$' + T);
SuffixArray sa = new SuffixArray(sb.toString().toCharArray());
int max = 0;
for (int i = 0; i < sb.length(); ++i) {
if (sa.sa[i] < S.length() != sa.sa[i + 1] < S.length())
max = Math.max(max, sa.lcp[i]);
}
System.out.println("Nejdelsi spolecny retezec ma delku " + max + ".");
}
}

class SuffixArray{
int k = 1;
int n;
Integer[] sa;
int[] rank, tmp;
int[] lcp;

SuffixArray(char[] cs){
n    = cs.length;
sa   = new Integer[n + 1];
rank = new int[n + 1];
tmp  = new int[n + 1];
lcp  = new int[n];
for (int i = 0; i <= n; ++i) {
sa[i] = i;
rank[i] = i < n ? cs[i] : -1;
}

for (k = 1; k <= n; k <<= 1) {
Arrays.sort(sa, cmp);
tmp[sa[0]] = 0;
for (int i = 1; i <= n; ++i) {
tmp[sa[i]] = tmp[sa[i - 1]] + (cmp.compare(sa[i - 1], sa[i]) < 0 ? 1 : 0);
}

for (int i = 0; i <= n; ++i) {
rank[i] = tmp[i];
}
}

// lcp
for (int i = 0; i <= n; ++i) rank[sa[i]] = i;  //求出每个后缀的当前排名
int h = 0;
for (int i = 0; i < n; ++i) {
int j = sa[rank[i] - 1]; // 后缀i的前一个后缀
if (h > 0) h--;
for (;j + h < n && i + h < n; ++h) {
if (cs[j + h] != cs[i + h]) break;
}
lcp[rank[i] -1] = h;
}

}

private Comparator<Integer> cmp = new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
int i = o1;
int j = o2;
if (rank[i] != rank[j]) return rank[i] - rank[j];
else {
int ri = i + k <= n ? rank[i + k] : -1;
int rj = j + k <= n ? rank[j + k] : -1;
return ri - rj;
}
}
};
}

void run() throws IOException {
}
}```

98 篇文章33 人订阅

0 条评论

## 相关文章

### 【编程题】Java编程题三（10道）

【编程题】Java编程题三（10道） 【程序21】 题目：求1+2!+3!+...+20!的和 public class lianxi21 { publ...

3526

1896

### python的字典和集合

dict类型可以说是python里模块的命名空间，实例的属性，函数的关键字参数都有其的参与。

923

34010

1960

### TypeScript学习笔记之类

TypeScript的类，简单地定义如下： class Person { x: number; // 默认为public类型 y: ...

2150

1972

### Scalaz（27）－ Inference & Unapply ：类型的推导和匹配

经过一段时间的摸索，用scala进行函数式编程的过程对我来说就好像是想着法儿如何将函数的款式对齐以及如何正确地匹配类型，真正是一种全新的体验，但好像有点太偏...

1958

523