思路：这题看了题解说是后缀数组做的，然后自己就偿试了一下，唉……没想到不管是不管是倍增算法的后缀还是DC3算法的后缀都T了，实在无计可施了，可能只有哗然可以过了。不过比赛那天题解说是没有卡后缀的。只是比赛那天自己还不会后缀数组，所以这题自己根本就没有看到。因为后缀自己练得还比较少，这题正好用RMQ求任意两个后缀之间的最长公共前缀，所以自己就拿这题练手了，虽然T了，但是倍增的算法和DC3的算法都贴上来吧，以配以后可能用得到。

倍增算法的代码：

#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#include<queue>
#include<set>
#include<cmath>
#include<bitset>
#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 10000005
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
void radix(int *str,int *a,int *b,int n,int m)
{
    static int count[maxn];
    mem(count,0);
    for(int i=0; i<n; i++) ++count[str[a[i]]];
    for(int i=1; i<=m; i++) count[i]+=count[i-1];
    for(int i=n-1; 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; i++) rank[i]=i;
    radix(str,rank,sa,n,m);
    rank[sa[0]]=0;
    for(int i=1; i<n; i++)
        rank[sa[i]]=rank[sa[i-1]]+(str[sa[i]]!=str[sa[i-1]]);
    for(int i=0; 1<<i<n; i++)
    {
        for(int j=0; j<n; j++)
        {
            a[j]=rank[j]+1;
            b[j]=j+(1<<i)>=n?0:rank[j+(1<<i)]+1;
            sa[j]=j;
        }
        radix(b,sa,rank,n,n);
        radix(a,rank,sa,n,n);
        rank[sa[0]]=0;
        for(int j=1; j<n; j++)
            rank[sa[j]]=rank[sa[j-1]]+(a[sa[j-1]]!=a[sa[j]]||b[sa[j-1]]!=b[sa[j]]);
    }
}
void calcHeight(int *str,int *sa,int *h,int *rank,int n) //求出最长公共前缀数组h
{
    int k=0;
    h[0]=0;
    for(int i=0; i<n; i++) rank[sa[i]]=i;
    for(int i=0; i<n; i++)
    {
        k=k==0?0:k-1;
        if(rank[i])
            while(str[i+k]==str[sa[rank[i]-1]+k]) k++;
        else k=0;
        h[rank[i]]=k;
    }
}
int a[maxn],sa[maxn],height[maxn],rank[maxn];
int dp[maxn][40];  //二维求的是任意两个height之间的最值
void RMQ_INIT(int n)
{
    mem(dp,0);
    for(int i=1; i<n; i++)
        dp[i][0]=height[i];
    for(int j=1; (1<<j)<=n; j++)
        for(int i=1; i+(1<<j)-1<n; i++)
            dp[i][j]=min(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
}
int RMQ(int l,int r)
{
    l=rank[l],r=rank[r];
    if(l>r) swap(l,r);
    l++; //为什么要加1呢，因为l是与l+1位置求的最长公共前缀
    //即height[l+1]=suffix(l+1)与suffix(l)的最长公共前缀
    int k=log(r-l+1.0)/log(2.0);
    return min(dp[l][k],dp[r-(1<<k)+1][k]);
}
char s[200005],ss[100005];
bool check(int st,int en,int len)
{
    int lcp=RMQ(st,en);
    lcp++;
    lcp+=RMQ(st+lcp,en+lcp);
    lcp++;
    lcp+=RMQ(st+lcp,en+lcp);
    if(en+lcp>=len) return true;
    return false;
}
int main()
{
    int t,ii=1;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%s%s",s,ss);
        int l1=strlen(s),l2=strlen(ss);
        if(l1<l2)
        {
            puts("-1");
            continue;
        }
        strcat(s,"$");
        strcat(s,ss);
        int len=strlen(s);
        copy(s,s+len,a);
        suffix(a,sa,len,128);
        calcHeight(a,sa,height,rank,len);
        int pos=-1;
        RMQ_INIT(len);
        for(int i=0;i<=l1-l2;i++)
            if(check(i,l1+1,len))
            {
                pos=i;
                break;
            }
        printf("Case #%d: %d\n",ii++,pos);
    }
    return 0;
}

DC3算法的代码：

#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#include<queue>
#include<set>
#include<cmath>
#include<bitset>
#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 10000005
#define F(x) ((x)/3+((x)%3==1?0:tb))
#define G(x) ((x)<tb?(x)*3+1:((x)-tb)*3+2)
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
int wa[maxn],wb[maxn],wv[maxn],wt[maxn];
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++) wt[i]=0;
    for(i=0; i<n; i++) wt[wv[i]]++;
    for(i=1; i<m; i++) wt[i]+=wt[i-1];
    for(i=n-1; i>=0; i--) b[--wt[wv[i]]]=a[i];
    return;
}
void dc3(int *r,int *sa,int n,int m)
{
    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;
    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;
    for(i=0; i<tbc; i++) if(san[i]<tb) wb[ta++]=san[i]*3;
    if(n%3==1) wb[ta++]=n-1;
    sort(r,wb,wa,ta,m);
    for(i=0; i<tbc; i++) wv[wb[i]=G(san[i])]=i;
    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;
}
int rank[maxn],height[maxn];
void calcHeight(int *r,int *sa,int n)
{
    int i,j,k=0;
    for(i=1; i<=n; i++) rank[sa[i]]=i;
    for(i=0; i<n; height[rank[i++]]=k)
        for(k?k--:0,j=sa[rank[i]-1]; r[i+k]==r[j+k]; k++);
    return;
}
int dp[maxn][40],a[maxn],sa[maxn];  //二维求的是任意两个height之间的最值
void RMQ_INIT(int n)
{
    mem(dp,0);
    for(int i=1; i<=n; i++)
        dp[i][0]=height[i];
    for(int j=1; (1<<j)<=n; j++)
        for(int i=1; i+(1<<j)-1<n; i++)
            dp[i][j]=min(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
}
int RMQ(int l,int r)
{
    l=rank[l],r=rank[r];
    if(l>r) swap(l,r);
    l++; //为什么要加1呢，因为l是与l+1位置求的最长公共前缀
    //即height[l+1]=suffix(l+1)与suffix(l)的最长公共前缀
    int k=log(r-l+1.0)/log(2.0);
    return min(dp[l][k],dp[r-(1<<k)+1][k]);
}
char s[200005],ss[100005];
bool check(int st,int en,int len)
{
    int lcp=RMQ(st,en);
    lcp++;
    lcp+=RMQ(st+lcp,en+lcp);
    lcp++;
    lcp+=RMQ(st+lcp,en+lcp);
    if(en+lcp>=len) return true;
    return false;
}
int main()
{
    int t,ii=1;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%s%s",s,ss);
        int l1=strlen(s),l2=strlen(ss);
        if(l1<l2)
        {
            puts("-1");
            continue;
        }
        strcat(s,"$");
        strcat(s,ss);
        int len=strlen(s);
        copy(s,s+len,a);
        dc3(a,sa,len+1,128);
        calcHeight(a,sa,len);
        int pos=-1;
        RMQ_INIT(len);
        for(int i=0; i<=l1-l2; i++)
            if(check(i,l1+1,len))
            {
                pos=i;
                break;
            }
        printf("Case #%d: %d\n",ii++,pos);
    }
    return 0;
}

BNUOJ 34990 北京邀请赛最后一题