这题要求两个串中的最长相同子串的长度。高度数组可以求一个串中的最长相同子串的长度。所以想到把两个串连起来，但是这样又会产生一些新的串（第一个串的结尾和第二个串的开头组成的）于是在两个串中间放一个'\0'分隔，正好'\0'是字符里最小的，不会对第一个串的排序产生影响。
| Accepted | 1403 | 62MS | 5344K | 2117 B | G++ |
#include "bits/stdc++.h"
using namespace std;
const int MAXN = 2e5 + ;
char s[MAXN];
int x[MAXN], y[MAXN], cnt[MAXN];
int sa[MAXN], rk[MAXN], height[MAXN];
int a, b, ans;
void getSa(int n, int m) {
for (int i = ; i <= m; i++) {
cnt[i] = ;
}
for (int i = ; i <= n; i++) {
cnt[x[i] = s[i]]++;
}
for (int i = ; i <= m; i++) {
cnt[i] += cnt[i - ];
}
for (int i = n; i; i--) {
sa[cnt[x[i]]--] = i;
}
int num = ;
for (int j = ; num < n; j <<= , m = num) {
num = ;
for (int i = n - j + ; i <= n; i++) {
y[++num] = i;
}
for (int i = ; i <= n; i++) {
if (sa[i] > j) {
y[++num] = sa[i] - j;
}
}
for (int i = ; i <= m; i++) {
cnt[i] = ;
}
for (int i = ; i <= n; i++) {
cnt[x[i]]++;
}
for (int i = ; i <= m; i++) {
cnt[i] += cnt[i - ];
}
for (int i = n; i; i--) {
sa[cnt[x[y[i]]]--] = y[i];
}
swap(x, y);
num = ;
x[sa[]] = ;
for (int i = ; i <= n; i++) {
if (y[sa[i]] != y[sa[i - ]] || y[sa[i] + j] != y[sa[i - ] + j]) {
x[sa[i]] = ++num;
} else {
x[sa[i]] = num;
}
}
}
}
void getHeight(int n) {
for (int i = ; i <= n; i++) {
rk[sa[i]] = i;
}
int k = ;
for (int i = ; i <= n; i++) {
int j = sa[rk[i] - ];
k = k ? k - : k;
while (s[i + k] == s[j + k]) {
k++;
}
// height[rk[i]] = k; // 如果i和j位于前后两个不同的串，更新ans
if ((i <= a + ) ^ (j <= a + )) {
ans = max(ans, k);
}
}
}
int main() {
while (~scanf("%s", s + )) {
a = strlen(s + );
// 把第二个字符串直接输入到第一个字符串的'\0'后面,例如输入两个"abc"就是"\0abc\0abc\0"
scanf("%s", s + a + );
b = strlen(s + a + );
// n表示第一个串的长度，m表示第二个串的长度，加上中间的'\0'要求后缀数组的部分长度为n + m + 1,也就是"abc\0abc"这部分
getSa(a + b + , );
ans = ;
// 在求高度数组的时候为避免第二个串后面的'\0'和第一个串后面的'\0'对结果造成影响。"abc\0" == "abc\0" 将第二个串后面的'\0'改成字符串中不可能出现的字符
s[a + b + ] = '';
getHeight(a + b + );
printf("%d\n", ans);
}
return ;
}