其实两道题差不多，只是这道题不只是找到两个字串的最长公共前缀，而且要输出这个公共的字串。
    那么我们可以在二分答案的时候记录他的首地址。而sa[]数组就可以帮助我们轻松的完成这个任务。
    我们只需要每次更新答案的时候，更新sa[]数组即可。
    最后输出一个长度为ans的最长公共字串即可。
    //ural 1517
    #include <iostream>
    #include <cstdio>
    #include <algorithm>
    #include <string>
    #include <cmath>
    #include <cstring>
    #include <queue>
    #include <set>
    #include <vector>
    #include <stack>
    #include <map>
    #include <iomanip>
    #define PI acos（-1.0）
    #define Max 2505
    #define inf 1《28
    #define LL（x） （ x 《 1 ）
    #define RR（x） （ x 《 1 | 1 ）
    #define REP（i,s,t） for（ int i = （ s ） ; i <= （ t ） ; ++ i ）
    #define mem（a,b） memset（a,b,sizeof（a））
    #define mp（a,b） make_pair（a,b）
    #define PII pair<int,int>
    using namespace std;
    #define N 200005
    /****后缀数组模版****/
    #define F（x）（（x）/3+（（x）%3==1 0:tb）） //F（x）求出原字符串的suffix（x）在新的字符串中的起始位置
    #define G（x）（（x）<tb （x）*3+1:（（x）-tb）*3+2） //G（x）是计算新字符串的suffix（x）在原字符串中的位置，和F（x）为互逆运算
    int wa[N],wb[N],wv[N],WS[N];
    int sa[N*3] ;
    int rank1[N],height[N];
    int r[N*3];
    int c0（int *r,int a,int b） {
    return r[a]==r[b] && r[a+1]==r[b+1] && r[a+2]==r[b+2];
    }
    int c12（int k,int *r,int a,int b） {
    if（k==2）
    return r[a]<r[b] || （ r[a]==r[b] && c12（1,r,a+1,b+1） ）；
    else
    return r[a]<r[b] || （ r[a]==r[b] && wv[a+1]<wv[b+1] ）；
    }
    void sort（int *r,int *a,int *b,int n,int m） {
    int i;
    for（i=0; i<n; i++）
    wv[i]=r[a[i]];
    for（i=0; i<m; i++）
    WS[i]=0;
    for（i=0; i<n; i++）
    WS[wv[i]]++;
    for（i=1; i<m; i++）
    WS[i]+=WS[i-1];
    for（i=n-1; i>=0; i--）
    b[--WS[wv[i]]]=a[i];
    return;
    }
    //注意点：为了方便下面的递归处理，r数组和sa数组的大小都要是3*n
    void dc3（int *r,int *sa,int n,int m） { //rn数组保存的是递归处理的新字符串，san数组是新字符串的sa
    int i , j , *rn = r+n , *san = sa+n , ta = 0 ,tb = （n+1）/3 , tbc = 0 , p;
    r[n] = r[n+1] = 0;
    for（i=0; i<n; i++） {
    if（i%3!=0）
    wa[tbc++]=i; //tbc表示起始位置模3为1或2的后缀个数
    }
    sort（r+2,wa,wb,tbc,m）；
    sort（r+1,wb,wa,tbc,m）；
    sort（r,wa,wb,tbc,m）；
    for（p=1,rn[F（wb[0]）]=0,i=1; i<tbc; i++）
    rn[F（wb[i]）]=c0（r,wb[i-1],wb[i]）？p-1:p++;
    if（p<tbc）
    dc3（rn,san,tbc,p）；
    else {
    for（i=0; i<tbc; i++）
    san[rn[i]]=i;
    }
    //对所有起始位置模3等于0的后缀排序
    for（i=0; i<tbc; i++） {
    if（san[i]<tb）
    wb[ta++]=san[i]*3;
    }
    if（n%3==1）  //n%3==1,要特殊处理suffix（n-1）
    wb[ta++]=n-1;
    sort（r,wb,wa,ta,m）；
    for（i=0; i<tbc; i++）
    wv[wb[i]=G（san[i]）]=i;
    //合并所有后缀的排序结果，保存在sa数组中
    for（i=0,j=0,p=0; i<ta&&j<tbc; p++）
    sa[p]=c12（wb[j]%3,r,wa[i],wb[j]）？wa[i++]:wb[j++];
    for（； i<ta; p++）
    sa[p]=wa[i++];
    for（； j<tbc; p++）
    sa[p]=wb[j++];
    return;
    }
    //height[i]=suffix（sa[i-1]）和suffix（sa[i]）的最长公共前缀，也就是排名相邻的两个后缀的最长公共前缀
    void calheight（int *r,int *sa,int n） {
    int i,j,k=0;
    for（i=1; i<=n; i++）
    rank1[sa[i]]=i;
    for（i=0; i<n; height[rank1[i++]]=k）
    for（k k--:0,j=sa[rank1[i]-1]; r[i+k]==r[j+k]; k++）；
    }
    char a[N] ;
    int ans = 0 ;
    int main（） {
    int x ;
    cin 》 x ;
    scanf（"%s",a） ;
    ans = 0 ;
    int l = strlen（a） ;
    a[l] = '*' ;
    scanf（"%s", a + l + 1） ;
    int ll = strlen（a） ;
    for （int i = 0 ; i < ll ; i ++ ）r[i] = （int）a[i] ;
    r[ll] = 0 ;
    dc3（r ,sa ,ll + 1,128） ;
    calheight（r , sa , ll） ;
    int now = -1 ;
    for （int i = 1 ; i <= ll ; i ++ ） {
    if（（sa[i] > l && sa[i - 1] < l ） || （sa[i] < l && sa[i - 1] > l） ） {//保证这个sa[i]和sa[i - 1]是位于不同的字符串中的
    if（ans < height[i]） {
    ans = height[i] ;
    now = sa[i - 1] ;
    }
    }
    }
    //cout 《 now 《 " " 《 ans 《 endl;
    for （int i = now ; i < now + ans ; i ++ ）cout 《 a[i] ;
    cout 《 endl;
    //cout 《 ans 《 endl;
    return 0 ;
    }