//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++）；
    }
    inline void RD（int &ret） {
    char c;
    do {
    c = getchar（）；
    } while（c < '0' || c > '9'） ;
    ret = c - '0';
    while（（c=getchar（）） >= '0' && c <= '9'）
    ret = ret * 10 + （ c - '0' ）；
    }
    inline void OT（int a）{
    if（a >= 10）OT（a / 10） ;
    putchar（a % 10 + '0'） ;
    }
    char a[N] ;
    int main（） {
    int T ;
    cin 》 T ;
    while（ T -- ）{
    cin 》 a ;
    int l = strlen（a） ;
    for （int i = 0 ; i < l ; i ++ ）r[i] = a[i] ;
    r[l] = 0 ;
    dc3（r , sa , l + 1 , 200） ;
    calheight（r , sa , l ） ;
    int ans = 0 ;
    for （int i = 1 ; i <= l ; i ++ ）{
    ans += l - sa[i] - height[i] ;
    }
    cout 《 ans 《 endl;
    }
    return 0 ;
    }
    例 6 :最长回文子串（ ural1297 ）
    给定一个字符串，求最长回文子串。
    [解法]:
    将整个字 符串反过来写在原字符串后面，中间用一个特殊的字符隔开。这样就把问题变为 了
    求这个新的字符串的某两个后缀的最长公共前缀。
    eg:aabebf ----> aabebf&fbebaa
    例 7 :连续重复子串 （pku2406）
    给定一个字符串 L ,已知这个字符串是由某个字符串 S 重复 R 次而得到的，
    求 R 的最大值。
    [解法]:
    做法比较简单，穷举字符串 S 的长度 k ,然后判断是否满足。判断的时候，
    先看字符串 L 的长度能否被 k 整除，再看 suffix（1） 和 suffix（k+1） 的最长公共
    前缀是否等于 n-k .
    hit:此题更好的是考察KMP的next
    int k=len-next[len];
    if（len%k==0） fprintf（fout,"%d\n",len/k）；
    else fprintf（fout,"1\n"）；
    例 8 :重复次数最多的连续重复子串 （spoj687,pku3693）
    给定一个字符串，求重复次数最多的连续重复子串。
    [解法]:
    先穷举长度 L ,然后求长度为 L 的子串最多能连续出现几次。首先连续出 现
    1 次是肯定可以的，所以这里只考虑至少 2 次的情况。假设在原字符串中连续 出
    现 2 次，记这个子字符串为 S ,那么 S 肯定包括了字符 r[0], r[L], r[L*2],
    r[L*3], …… 中的某相邻的两个。所以只须看字符 r[L*i] 和 r[L*（i+1）] 往前和
    往后各能匹配到多远，记这个总长度为 K ,那么这里连续出现了 K/L+1 次。最 后
    看最大值是多少。
    例 9 :最长公共子串 （pku2774,ural1517）
    给定两个字符串 A 和 B ,求最长公共子串。
    连接字符串，O（N）扫描
    //POJ 2774 HDU 1403
    #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（） {
    while（scanf（"%s",a） != EOF） {
    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） ;
    for （int i = 1 ; i <= ll ; i ++ ） {
    if（（sa[i] > l && sa[i - 1] < l ） || （sa[i] < l && sa[i - 1] > l） ） {
    ans = max（ans ,height[i]） ;
    }
    }
    cout 《 ans 《 endl;
    }
    return 0 ;
    }