后缀数据结构模板

 1 struct SAM
 2 {
 3     struct node
 4     {
 5         node*f;
 6         node*s[26];
 7         int v;
 8         node(const node*f)
 9         { memcpy(this,f,sizeof(node)); }
10         node(int _v)
11         { f=NULL; memset(s,0,sizeof(s)); v=_v; }
12     };
13     
14     node*root,*last;
15     
16     SAM(){root=last=new node(0);}
17     
18     void expend(int v) //add a value v to the tail of current string.
19     {
20         node*p=last; //p--t
21         node*t=new node(p->v+1);
22         
23         while(p && !p->s[v])
24             p->s[v]=t, p=p->f;
25         
26         if(!p) t->f=root;
27         else
28         {
29             node*q=p->s[v]; //q--h
30             if(p->v+1==q->v)
31                 t->f=q;
32             else
33             {
34                 node*h=new node(q);
35                 t->f=q->f=h;
36                 while(p && p->s[v]==q)
37                     p->s[v]=h, p=p->f;
38             }
39         }
40         last=t;
41     }
42 };
43 
44 
45 int main()
46 {
47     SAM T;
48     string s;
49     cin>>s;
50     for(int i=0;i<s.size();i++)
51     T.expend(s[i]-‘a‘);
52     
53     while(cin>>s)
54     {
55         SAM::node*x=T.root;
56         for(int i=0;i<s.size();i++)
57         if(x!=NULL) x=x->s[s[i]-‘a‘];
58         printf("%d\n",!(!x));        
59     }
60     
61     return 0;
62 }