CF 149E Martian Strings 后缀自动机

这里给出来一个后缀自动机的题解.

考虑对 $s$ 的正串和反串分别建后缀自动机.

对于正串的每个节点维护 $endpos$ 的最小值.

对于反串的每个节点维护 $endpos$ 的最大值.

这两个东西通过一个简单的基数排序就可以实现.

将 $p$ 的正串在正串的 SAM 上去匹配，一直
匹配到匹配不了为止，并记录 $p[i]$ 在正串中自动机节点上 $endpos$ 的最小值 $a[i]$.

对 $p$ 的反串也进行相同的处理，记录 $endpos$ 的最大值 $b[i]$.

正串中的 $endpos$ 就是 $p[1...i]$ 中 $i$ 的最小结束位置，那么反串中的 $endpos$ 就是 $p[i...length(p)]$ 中 $i$ 的最大开始位置.

所以，我们只需枚举 $1$~length(p) 并判断 $a[i]&&b[i]&&a[i]<b[i+1]$ 即可.

如果满足这个条件，就说明这个询问是有解的.

当然，要注意判断一下长度为 $1$ 的情况，这显然是无解的.

#include <cstdio>

#include <cstring>

#include <algorithm>

#define N 200004

#define setIO(s) freopen(s".in","r",stdin)

using namespace std;

inline void getmin(int &a,int b) { if(b<a)a=b; }

inline void getmax(int &a,int b) { if(b>a)a=b; }

int a[1002],b[1002],n;

char str[N],P[N];

struct SAM

{

    int c[N],rk[N],tot,last;

    struct Node { int len,ch[27],f,minv,maxv; }t[N];

    void init() { last=tot=1; }

    inline void extend(int c,int lst)

    {

        int np=++tot,p=last;

        last=np, t[np].len=t[p].len+1;

        while(p&&!t[p].ch[c]) t[p].ch[c]=np,p=t[p].f;

        if(!p) t[np].f=1;

        else

        {

            int q=t[p].ch[c];

            if(t[q].len==t[p].len+1) t[np].f=q;

            else

            {

                int nq=++tot;

                t[nq].len=t[p].len+1,t[nq].minv=t[nq].maxv=t[q].maxv;

                memcpy(t[nq].ch,t[q].ch,sizeof(t[q].ch));

                t[nq].f=t[q].f,t[q].f=t[np].f=nq;

                while(p&&t[p].ch[c]==q) t[p].ch[c]=nq,p=t[p].f;

            }

        }

        t[np].minv=t[np].maxv=lst;

    }

    inline void prepare()

    {

        int i,u;

        for(i=1;i<=tot;++i) c[i]=0;

        for(i=1;i<=tot;++i) ++c[t[i].len];

        for(i=1;i<=tot;++i) rk[c[t[i].len]--]=i;

        for(i=tot;i>=1;--i)

            u=rk[i],getmin(t[t[u].f].minv,t[u].minv),getmax(t[t[u].f].maxv,t[u].maxv);

    }

}t1,t2;

int main()

{

    int i,j,m,re=0,ans=0;

    // setIO("input");

    t1.init(),t2.init();

    scanf("%s",str+1),n=strlen(str+1);

    for(i=1;i<=n;++i) t1.extend(str[i]-'A',i);

    for(i=n;i>=1;--i) t2.extend(str[i]-'A',i);

    t1.prepare(),t2.prepare(),scanf("%d",&m);

    for(i=1;i<=m;++i)

    {

        int len,p;

        scanf("%s",P+1),len=strlen(P+1),memset(a,0,sizeof(a)),memset(b,0,sizeof(b));

        for(p=j=1;j<=len;++j)

        {

            int c=P[j]-'A';

            if(t1.t[p].ch[c]) a[j]=t1.t[t1.t[p].ch[c]].minv,p=t1.t[p].ch[c]; else break;

        }

        for(p=1,j=len;j>=1;--j)

        {

            int c=P[j]-'A';

            if(t2.t[p].ch[c]) b[j]=t2.t[t2.t[p].ch[c]].maxv,p=t2.t[p].ch[c]; else break;

        }

        re=0;

        for(j=1;j<len;++j) {

            if(a[j]&&b[j+1]&&a[j]<b[j+1]) re=1;

        }

        if(a[len]) re=1;

        if(len==1) re=0;

        ans+=re;

    }

    printf("%d\n",ans);

    return 0;

}