stl的vector太慢了

还是手写的好

upd: 有一件很神奇的事情，就是我第一次pb的时候会分配0的空间，似乎是不对的，但我已经用了多次且没有出锅。。。

但还是多分配一个空间好了

#include<bits/stdc++.h>
using namespace std;

template<typename T>
struct vec
{
T *a;
int n;
void clear()
{
   //if (n>0) {free(a);a=0;}
    n=0;
}
void pb(const T &x)
{
    if((n&-n)==n)//a=(T*)realloc(a,(n*2+1)*sizeof(T));
    {
        T *_a=new T [n*2+1];
        memcpy(_a,a,n*sizeof(T));
        a=_a;
    }
    a[n++]=x;
}
};
vec<int> a;
#define fore(arr) for(auto it=arr.a,end=it+arr.n;it!=end;++it)

int main()
{
     a.pb(1);
    fore(a) printf("%d\n",*it);
    a.clear();
    a.pb(2);
    fore(a) printf("%d\n",*it);
}

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

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);
        }
    }
}

$O(nlogn)$版

要注意:
计数排序后面一定要逆序加回去，这样才能保证原来的顺序不被破坏

int sa[N],q1[N],q2[N],*rank=q1,*temp=q2;
//sa[i] suffix array 后缀数组 第i名的起始位置
//rank[i] 第i个起始位置的rank 
char s[N];
int num[N];

int n,i;
void get_sa()
{
    int m=255;
    for (i=1;i<=n;++i) ++num[s[i]];
    for (i=1;i<=m;++i) num[i]+=num[i-1];
    for (i=n;i;--i) sa[num[s[i]]--]=i;
    int last,now;
    m=rank[last=sa[1]]=1;
    for (i=2;i<=n;++i) 
    {
        now=sa[i];
        if (s[now]!=s[last]) ++m;
        rank[last=now]=m;
    }

    for (int l=1;m<n;l<<=1)//rank[i],rank[i+l]作关键字
    {
        //先以rank[i+l]作关键字排序 
        int top=0;
        //i>n-l的 i+l已经超出 直接放进来 
        for (i=n-l+1;i<=n;++i) temp[++top]=i;
        //i<=n-l的 可以利用上一次的sa
        for (i=1;i<=n;++i)
        if (sa[i]>l) temp[++top]=sa[i]-l;

        //在temp的基础上 以rank[i]为关键字 计数排序 
        memset(num,0,m+1<<2);
        for (i=1;i<=n;++i) ++num[rank[i]];
        for (i=2;i<=m;++i) num[i]+=num[i-1];
        for (i=n;i;--i) sa[num[rank[temp[i]]]--]=temp[i];

        std::swap(rank,temp);//temp存储原来的rank,来比较是否一样
        m=rank[last=sa[1]]=1;
        for (i=2;i<=n;++i)
        {
            now=sa[i];
            if (!(temp[now]==temp[last]&&temp[now+l]==temp[last+l])) ++m;
            rank[last=now]=m; 
        }
    } 
}