紫书习题的代码，虽然能ac，但是板子有问题，如果输入，就会错，我在别的博客修改了板子戳我传送，这里懒得改了（毕竟紫书的板子只要输入的字符串的字符种类大于1就不会错）。
78ms代码：

#include<bits/stdc++.h>
using namespace std;
const int MAXN=200005;                    //字符串的长度
char s[MAXN];                            //输入字符串
int sa[MAXN],cnt[MAXN],t1[MAXN],t2[MAXN],rk[MAXN],height[MAXN];
int n;

void calc_sa(){                                //n是字符串长度 
    int m=127;                                //m是小写字母的ASCII码值范围，构成字符串s的后缀数组，每个字符的值必须为0~m-1
    int i,*x=t1,*y=t2;
    for(i=0;i<m;i++)    cnt[i]=0;
    for(i=0;i<n;i++)    cnt[x[i]=s[i]]++;
    for(i=1;i<m;i++)    cnt[i]+=cnt[i-1];
    for(i=n-1;i>=0;i--)    sa[--cnt[x[i]]]=i;
    //sa[]:从0到n-1
    for(int k=1;k<=n;k*=2){                    //利用对长度为k的排序结果对长度为2k的排序 
        int p=0;
        //2nd
        for(i=n-k;i<n;i++)    y[p++]=i;
        for(i=0;i<n;i++)    if(sa[i]>=k)    y[p++]=sa[i]-k;
        //1st
        for(i=0;i<m;i++)    cnt[i]=0;
        for(i=0;i<n;i++)    cnt[x[y[i]]]++;
        for(i=1;i<m;i++)    cnt[i]+=cnt[i-1];
        for(i=n-1;i>=0;i--)    sa[--cnt[x[y[i]]]]=y[i];
        swap(x,y);
        p=1; x[sa[0]]=0;
        for(i=1;i<n;i++)
            x[sa[i]]=y[sa[i-1]]==y[sa[i]]&&y[sa[i-1]+k]==y[sa[i]+k]?p-1:p++;
        if(p>=n)    break;
        m=p;
    } 
}
void getheight(){                        //n是字符串长度 
    int i,j,k=0;
    for(i=0;i<n;i++)    rk[sa[i]]=i;    //用sa[]推导rk[] 
    for(i=0;i<n;i++){
        if(k)    k--;
        int j=sa[rk[i]-1];
        while(s[i+k]==s[j+k])    k++;
        height[rk[i]]=k;
    }
}
int main(){
    int len1,ans;
    while(scanf("%s",s)!=EOF){
        n=strlen(s);
        len1=n;
        s[n]='$';
        scanf("%s",s+n+1);
        n=strlen(s);
        calc_sa();
        getheight();
        ans=0;
        for(int i=1;i<n;i++)
            if(height[i]>ans&&((sa[i-1]<len1&&sa[i]>=len1)||(sa[i-1]>=len1&&sa[i]<len1)))
                ans=height[i];
        printf("%d\n",ans);
    }
    return 0;
}

800ms代码：

#include<bits/stdc++.h>
using namespace std;
const int MAXN=200005;                    //字符串的长度
char s[MAXN];                            //输入字符串
int sa[MAXN],rk[MAXN],tmp[MAXN+1],height[MAXN];
int n,k;

/*比较函数
每一步使得 sa[]从0到n-1对应的字符串（从sa[i]开始的字串）按照组合数大小从小到大排序
最后一步使得sa[]从0到n-1对应的字符串（从sa[i]开始的字串）按照字典序从小到大排列*/
bool comp_sa(int i,int j){                //组合数有两个部分，高位是rk[i],低位是rk[i+k]
    if(rk[i]!=rk[j])                    //先比较高位：rk[i]和rk[j]
        return rk[i]<rk[j];
    else{                                //高位相等，再比较低位的rk[i+k]和rk[j+k]
        int ri = i+k<=n? rk[i+k] : -1;
        int rj = j+k<=n? rk[j+k] : -1;
        return ri<rj;
    }
}
void calc_sa(){                            //计算字符串s的后缀数组
    for(int i=0;i<=n;i++){
        rk[i]=s[i];                        //字符串的原始数值
        sa[i]=i;                        //后缀数组，在每一步记录当前排序后的结果
    }
    for(k=1;k<=n;k*=2){                    //开始一步步操作，每一步递增两倍进行组合
        sort(sa,sa+n,comp_sa);            //排序，结果记录在sa[]中(根据rk[]值的大小（各个字串的大小）从小到大将rk[]的下标（从第几个字符开始的）存在sa[]中)
        tmp[sa[0]]=0;                    //rk[sa[i]]=i;
        for(int i=0;i<n;i++)            //用sa[]倒推组合数，并记录在tmp[]中，用于临时存放rk[]的新值
            tmp[sa[i+1]]= tmp[sa[i]] + (comp_sa(sa[i],sa[i+1])?1:0);        //(排序后sa[i+1]大于或等于sa[i])
        for(int i=0;i<n;i++)            //把tmp[]复制给rk[]，用于下一步操作
            rk[i] = tmp[i];                //每一步改变最高位 ，最后一步得到每个字串的排名
    }
}
void getheight(){                        //n是字符串长度 
    int i,j,k=0;
    for(i=0;i<n;i++){
        if(k)    k--;
        int j=sa[rk[i]-1];
        while(s[i+k]==s[j+k])    k++;
        height[rk[i]]=k;
    }
}
int main(){
    int len1,ans;
    while(scanf("%s",s)!=EOF){
        n=strlen(s);
        len1=n;
        s[n]='$';
        scanf("%s",s+n+1);
        n=strlen(s);
        calc_sa();
        getheight();
        ans=0;
        for(int i=1;i<n;i++)
            if(height[i]>ans&&((sa[i-1]<len1&&sa[i]>=len1)||(sa[i-1]>=len1&&sa[i]<len1)))
                ans=height[i];
        printf("%d\n",ans);
    }
    return 0;
}