题目大意：给出两个字符串，求出这两个字符串的最长公共序列。

思路：把两个字符串合成一个，然后跑一次后缀数组，求出rank数组和height数组，之后验证是否rank临近的两个后缀在不同的串里，如果是的话就更新答案。

CODE：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define MAX 2000100
using namespace std;

char s[MAX],_s[MAX];
int len,_len;

int sa[MAX],val[MAX],rank[MAX],height[MAX];
int ans;

inline bool Same(int x,int y,int l)
{
	return val[x] == val[y]
	&& ((x + l >= len && y + l >= len) || (x + l < len && y + l < len && val[x + l] == val[y + l]));
}

void GetSuffixArray()
{
	static int _val[MAX],q[MAX],cnt[MAX],lim = 300;
	for(int i = 0; i < len; ++i)	++cnt[val[i] = s[i]];
	for(int i = 1; i < lim; ++i)	cnt[i] += cnt[i - 1];
	for(int i = len - 1; i >= 0; --i)	sa[--cnt[val[i]]] = i;
	for(int d = 1;; ++d) {
		int top = 0,l = 1 << (d - 1);
		for(int i = 0; i < len; ++i)	if(sa[i] + l >= len)	q[top++] = sa[i];
		for(int i = 0; i < len; ++i)	if(sa[i] >= l)	q[top++] = sa[i] - l;
		
		for(int i = 0; i < lim; ++i)	cnt[i] = 0;
		for(int i = 0; i < len; ++i)	++cnt[val[q[i]]];
		for(int i = 1; i < lim; ++i)	cnt[i] += cnt[i - 1];
		for(int i = len - 1; i >= 0; --i)	sa[--cnt[val[q[i]]]] = q[i];
		lim = 0;
		for(int i = 0,j; i < len; ++lim) {
			for(j = i; j < len - 1 && Same(sa[j],sa[j + 1],l); ++j);
			for(; i <= j; ++i)	_val[sa[i]] = lim;
		}
		for(int i = 0; i < len; ++i)	val[i] = _val[i];
		if(lim == len)	break;
	}
	return ;
}

void GetHeight()
{
	for(int i = 0; i < len; ++i)
		rank[sa[i]] = i;
	for(int i = 0; i < len; ++i) {
		if(!rank[i])	continue;
		int j = 0;
		if(i)	j = max(0,height[rank[i - 1]] - 1);
		for(; i + j < len && sa[rank[i] - 1] + j < len && s[i + j] == s[sa[rank[i] - 1] + j]; ++j);
		height[rank[i]] = j;
	}
}

int main()
{
	scanf("%s%s",s,_s);
	_len = len = strlen(s);
	s[len] = '$';
	int __len = strlen(_s);
	for(int i = 0; i < __len; ++i)
		s[len + i + 1] = _s[i];
	s[len + strlen(_s) + 1] = '\0';
	len = strlen(s);
	GetSuffixArray();
	GetHeight();
	for(int i = 1; i < len; ++i)
		if(sa[i] < _len && sa[i - 1] > _len || (sa[i] > _len && sa[i - 1] < _len))
			ans = max(ans,height[i]);
	cout << ans << endl;
	return 0;
}

POJ 2774 Long Long Message 后缀数组