https://wenku.baidu.com/view/ed1be61e10a6f524ccbf85fd.html
题意：求两个串的最长公共子串
思路：在求出height数组之后，再把sa数组区分出来，只要其中一个sa[i] (s[i -1])数组是属于第一串，s[i - 1] (s[i])属于第二串，那么我们可以求得其最大值，之所以可以这样做，是因为sa数组已经对字符串按字典序排好序了


#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
const int maxn = 2e6 + 5;
char s1[maxn], s2[maxn], s[maxn];
int n, p1, p2, m, p;
int tx[maxn], sa[maxn], rak[maxn];
int height[maxn];
struct node {
	int x, y, id;
}a[maxn], b[maxn];

void rsort() {
	for (int i = 1; i <= m; i++) {
		tx[i] = 0;
	}
	for (int i = 1; i <= n; i++) {
		tx[a[i].y]++;
	}
	for (int i = 1; i <= m; i++) {
		tx[i] += tx[i - 1];
	}
	for (int i = 1; i <= n; i++) {
		b[tx[a[i].y]--] = a[i];
	}
	for (int i = 1; i <= m; i++) {
		tx[i] = 0;
	}
	for (int i = 1; i <= n; i++) {
		tx[b[i].x]++;
	}
	for (int i = 1; i <= m; i++) {
		tx[i] += tx[i - 1];
	}
	for (int i = n; i >= 1; i--) {
		a[tx[b[i].x]--] = b[i];
	}
}

void solve() {
	rsort();
	p = 0;
	for (int i = 1; i <= n; i++) {
		if (a[i].x == a[i - 1].x && a[i].y == a[i - 1].y) {
			rak[a[i].id] = p;
		} else {
			rak[a[i].id] = ++p;
		}
	}
	for (int i = 1; i <= n; i++) {
		a[i].x = rak[i];
		a[i].id = sa[rak[i]] = i;
		a[i].y = 0;
	}
	m = p;
}
void ssort() {
	m = 127;
	for (int i = 1; i <= n; i++) {
		a[i].x = a[i].y = s[i];
		a[i].id = i;
	}
	solve();
	for (int j = 1; j <= n; j <<= 1) {
		for (int i = 1; i + j <= n; i++) {
			a[i].y = a[i + j].x;
		}
		solve();
		if (p == n) {
			break;
		}
	}
}	

void get_Height() {
	int k = 0;
	for (int i = 1; i <= n; i++) {
		if (k) {
			k--;
		}
		int j = sa[rak[i] - 1];
		while (s[i + k] == s[j + k]) {
			k++;
		}
		height[rak[i]] = k;
	}
}

int main() {
	scanf("%s", s1 + 1);
	scanf("%s", s2 + 1);
	p1 = strlen(s1 + 1);
	p2 = strlen(s2 + 1);
	for (int i = 1; i <= p1; i++) {
		s[++n] = s1[i];
	}
	s[++n] = '#';
	for (int i = 1; i <= p2; i++) {
		s[++n] = s2[i];
	}
	ssort();
	get_Height();
	int ans = 0;
	for (int i = 2; i <= n; i++) {
		if (height[i] > ans) {
			if ((sa[i] < p1 && sa[i - 1] > p1) || (sa[i] > p1 && sa[i - 1] < p1)) {
				ans = height[i];
			}
		}
	}
	printf("%d\n", ans);
	return 0;
}