学步园

定义:

CH 取数据范围

const int NODE = 105 , CH = 4 ,mod = 100000;

int ch[NODE][CH], val[NODE] ,sz , fail[NODE];

初始化:

只要清空ch[0],注意sz是从1开始;

void init()
{
    sz=1;
    memset(ch[0],0,sizeof(ch[0]));
}

插入:

void insert(char *s)
{
    int u=0;
    for(;*s;s++)
    {
        int c=idx(*s);
        if(!ch[u][c])
        {
            memset(ch[sz],0,sizeof(ch[sz]));
            val[sz]=0;
            ch[u][c]=sz++;
        }
        u=ch[u][c];
    }
    val[u]=1;
}

重头戏:

int queue[MAXN];
void getfail()
{
    int *rear=queue,*front=queue;
    
    for(int c=0;c<CH;c++)
    {
        int u=ch[0][c];
        if(u)
            *rear++=u,f[u]=0,last[u]=0;
    }
    
    while(rear!=front)
    {
        int cur = front++;
        for(int c=0;c<CH;c++)
        {
            int &u = ch[cur][c];
            int tf=ch[f[cur]][c];
            if(!u)
            {
                u=tf;
                continue;
            }
            f[u]=tf;
            last[u]=val[f[u]]?f[u]:last[f[u]];
            *rear++=u;
        }
    }
}

接下来就是询问..

int find(char *s)
{
    int sum=0;
    int u=0;
    for(;*s;s++)
    {
        int c=idx(*s);
        u=ch[u][c];
        int next=0;
        if(val[u])
            next=u;
        else if(last[u])
            next=last[u];
        for(int tmp=next;tmp;tmp=last[tmp])
            sum+=val[tmp];
    }
    return sum;
}