没有题解我来发一个。(同时来存模板)

http://acm.fzu.edu.cn/problem.php?pid=2246

第1种情况，t直接出现在s中。

那么要么割前面要么割后面。

求出t在s中第一次出现的位置和最后一次出现的位置即可。

第2种情况，t分成两半出现在s中。

那么枚举被分成哪两半，求出前缀在s中第一次出现的位置和后缀在s中最后一次出现的位置即可。

要求m个串的所有前缀在s中第一次出现的位置，建ac自动机，让s跑一遍就好了。

后缀的话全反过来做一遍就好了。

要注意: ac自动机中fail[i]不一定<i, 但深度顺序或者bfs序一定<i。(因为是i的后缀)

#include<cstdio>
#include<vector>
#include<algorithm>
#include<cstring>
#include<iostream>
//#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
#define mid (l+r>>1)
#define pb push_back
#define rep(i,l,r) for(int i=l;i<=r;++i)
#define per(i,r,l) for(int i=r;i>=l;--i)

template <typename T> inline void chmin(T &x,const T &y)
{
    if(x>y)x=y;
}
template <typename T> inline void chmax(T &x,const T &y)
{
    if(x<y)x=y;
}

#define gc (c=getchar())
int read()
{
    char c;
    while(gc<'-');
    if(c=='-')
    {
        int x=gc-'0';
        while(gc>='0')x=x*10+c-'0';
        return -x;
    }
    int x=c-'0';
    while(gc>='0')x=x*10+c-'0';
    return x;
}

struct vec
{
    int *a,n;
    void pb(int x)
    {
        if((n&-n)==n)
        {
            int *_a=new int [n*2];
            memcpy(_a,a,n*sizeof(int));
            a=_a;
        }
        a[n++]=x;
    }
};
#define fore(arr) for(int *it=arr.a,*end=arr.a+arr.n;it!=end;++it)

const int N=1e5+500;
char s[N],T[N*2];int mn1[N*2],mn2[N],t[N],len[N];

int fail[N],ch[N][26],mn[N];int tot;
void ins(char *s)
{
    int i=1;
    for(char *c=s;*c>'0';++c)
    {
        int &to=ch[i][*c-'a'];
        i=to?to:(to=++tot);
    }
}
int q[N],tail;
void init_fail()
{
    tail=1;q[1]=1;
    for(int head=1;head<=tail;++head)
    {
        int i=q[head];
        int f=fail[i];
        rep(j,0,26-1)
        if(ch[i][j]) fail[q[++tail]=ch[i][j]]=ch[f][j];
        else ch[i][j]=ch[f][j];
    }
}
void travel(char *s)
{
    memset(mn+1,1<<5,tot*sizeof(int));
    int i=1,l=0;
    for(char *c=s;*c>'0';++c,++l) chmin(mn[i=ch[i][*c-'a']],l);
    for(int i=tot;i;--i) chmin(mn[fail[q[i]]],mn[q[i]]);
}
void Get(int *f,char *s)
{
    int i=1,l=0;
    for(char *c=s;*c>'0';++c,++l)
    {
        i=ch[i][*c-'a'];
        f[l]=mn[i];
    }
}

int main()
{
    freopen("1.in","r",stdin);freopen("1.out","w",stdout);
    int tt=read();
    rep(j,0,25)ch[0][j]=1;
    while(tt--)
    {
        scanf("%s",s);
        int n=strlen(s);

        memset(ch+1,0,tot*sizeof(*ch));
        tot=1;

        int m;
        cin>>m;
        int nt=0;
        rep(i,1,m) 
        {
            scanf("%s",T+(t[i]=nt));
            len[i]=strlen(T+nt);
            ins(T+nt);
            nt+=len[i]+1;
        }
        init_fail();

        travel(s);
        rep(i,1,m) 
        {
            Get(mn1+t[i],T+t[i]);
        }

        reverse(s,s+n);
        rep(i,1,m) reverse(T+t[i],T+t[i]+len[i]);

        memset(ch+1,0,tot*sizeof(*ch));
        tot=1;

        rep(i,1,m) ins(T+t[i]);
        init_fail();

        travel(s);
        rep(i,1,m) 
        {    
           Get(mn2,T+t[i]);
           int l=len[i],*mn=mn1+t[i];
           int ans=max(n-1-mn[l-1],n-1-mn2[l-1]);
           rep(j,1,l-1) 
            chmax(ans, n-(mn[j-1]+1+mn2[l-1-j]+1) );
           if(ans<0) puts("-1");
           else printf("%d\n",ans);
        }
    }
}