思路：其实很简单，就是两个字符串连接起来，中间用个特殊字符隔开，然后用后缀数组求最长公共前缀，然后不同在两个串中，并且最长的就是最长公共子串了。
注意的是：用第一个字符串来判断是不是在同一个字符中，刚开始用了第二个字符的长度来判断WA了2发才发现。
#include #include #include #include #include #include #include #include #include #define mem(a,b) memset(a,b,sizeof(a)) #define lson i<<1,l,mid #define rson i<<1|1,mid+1,r #define llson j<<1,l,mid #define rrson j<<1|1,mid+1,r #define INF 0x7fffffff #define maxn 200010 using namespace std; typedef long long ll; typedef unsigned long long ull; void radix(int *str,int *a,int *b,int n,int m) { static int count[maxn]; mem(count,0); for(int i=0; i =0; i--) b[--count[str[a[i]]]]=a[i]; } void suffix(int *str,int *sa,int n,int m) //倍增算法计算出后缀数组sa { static int rank[maxn],a[maxn],b[maxn]; for(int i=0; i =n?0:rank[j+(1< >s>>ss) { ss=s+"#"+ss; copy(ss.begin(),ss.end(),a); int n=ss.size(),len=0; suffix(a,sa,n,256); calcHeight(a,sa,height,rank,n); for(int i=1; i len&&((sa[i]