后缀自动机

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
//所建节点个数为2*n
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <queue>
#define FOR(i,l,r) for(int i=(l);i<=(r);i++)
#define FORD(i,r,l) for(int i=(r);i>=(l);i--)
#define rep(i,n) for(int i=0;i<(n);i++)
#define res(i,s) for(int i=0;((s)[i]);i++)
using namespace std;
typedef long long LL;
const int maxn=50001;

char s[maxn];
int k;

struct sam{
    sam *o[10],*f;
    int val;
    LL v[32];
}ssam[maxn*2],*bt,*last; int sct;
sam *newd(int val)
{
    sam *p=&ssam[sct++];
    rep(i,10) p->o[i]=0;
    p->f=0; p->val=val;
    rep(i,k) p->v[i]=0;
    return p;
}
void trans(char s)
{
    int d=s-'0';
    sam *p=last,*np=newd(p->val+1); last=np;
    for (; p&&!p->o[d]; p=p->f) p->o[d]=np;
    if (!p) np->f=bt;
    else if (p->o[d]->val==p->val+1) np->f=p->o[d];
    else
    {
        sam *q=p->o[d],*nq=newd(p->val+1);
        memcpy(nq->o,q->o,sizeof(q->o));//最好不要用memcpy，而是写成o数组的赋值
        nq->f=q->f; q->f=np->f=nq;
        for (; p&&p->o[d]==q; p=p->f) p->o[d]=nq;
    }
}
void init() { sct=0; last=bt=newd(0); }
}}}

//所建节点个数为2*n
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <queue>
#define FOR(i,l,r) for(int i=(l);i<=(r);i++)
#define FORD(i,r,l) for(int i=(r);i>=(l);i--)
#define rep(i,n) for(int i=0;i<(n);i++)
#define res(i,s) for(int i=0;((s)[i]);i++)
using namespace std;
typedef long long LL;
const int maxn=50001;
char s[maxn];
int k;
struct sam{
    sam *o[10],*f;
    int val;
    LL v[32];
}ssam[maxn*2],*bt,*last; int sct;
sam *newd(int val)
{
    sam *p=&ssam[sct++];
    rep(i,10) p->o[i]=0;
    p->f=0; p->val=val;
    rep(i,k) p->v[i]=0;
    return p;
}
void trans(char s)
{
    int d=s-'0';
    sam *p=last,*np=newd(p->val+1); last=np;
    for (; p&&!p->o[d]; p=p->f) p->o[d]=np;
    if (!p) np->f=bt;
    else if (p->o[d]->val==p->val+1) np->f=p->o[d];
    else
    {
        sam *q=p->o[d],*nq=newd(p->val+1);
        memcpy(nq->o,q->o,sizeof(q->o));//最好不要用memcpy，而是写成o数组的赋值
        nq->f=q->f; q->f=np->f=nq;
        for (; p&&p->o[d]==q; p=p->f) p->o[d]=nq;
    }
}
void init() { sct=0; last=bt=newd(0); }