bzoj 3172: [Tjoi2013]单词

.

题意：n个单词构成一篇文章（按顺序排成一排），问每个单词出现几次（成为其他单词的字串也算）
题解：SAM
求end-pos集合的大小。
代码：

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

struct SAM
{
    struct Node
    {
        int max,es,in;
        Node *next,*ch[27];
        Node(int max=0):next(NULL),ch(),max(max),es(1),in(0){}
    }*start,*last;
    vector<Node*>a;
    SAM()
    {
        start=last=new Node;
    }
    void extend(int c)
    {
        Node *u=new Node(last->max+1),*v=last;
        a.push_back(u);
        while(v&&!v->ch[c])
        {
            v->ch[c]=u;
            v=v->next;
        }
        if(!v)
            u->next=start;
        else if(v->ch[c]->max==v->max+1)
            u->next=v->ch[c];
        else
        {
            Node *n=new Node(v->max+1),*o=v->ch[c];
            a.push_back(n);
            n->es=0;
            for(int i=0;i<27;i++)
                n->ch[i]=o->ch[i];
            n->next=o->next;
            o->next=u->next=n;
            while(v&&v->ch[c]==o)
            {
                v->ch[c]=n;
                v=v->next;
            }
        }
        last=u;
    }
    void wk()
    {
        int sz=a.size();
        for(int i=0;i<sz;i++)
        if(a[i]->next)
        a[i]->next->in++;
        queue<Node*>q;
        for(int i=0;i<sz;i++)
        if(a[i]->in==0)
        q.push(a[i]);
        while(!q.empty())
        {
            Node *x=q.front();
            q.pop();
            if(x->next)
            {
                x->next->es+=x->es;
                x->next->in--;
                if(!x->next->in)
                q.push(x->next);
            }
        }
    }
    int fd(char *s)
    {
        Node *now=start;
        int len=strlen(s);
        for(int i=0;i<len;i++)
        now=now->ch[s[i]-'a'];
        return now->es;
    }
}sam;
int n,len[210];
char s[210][1000010];

int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        scanf("%s",s[i]);
        len[i]=strlen(s[i]);
        for(int j=0;j<len[i];j++)
        sam.extend(s[i][j]-'a');
        sam.extend(26);
    }
    sam.wk();
    for(int i=0;i<n;i++)
    printf("%d\n",sam.fd(s[i]));
}