HDU 4622 Reincarnation 后缀自动机

模板来源：http://blog.csdn.net/zkfzkfzkfzkfzkfzkfzk/article/details/9669747

解法参考：http://blog.csdn.net/dyx404514/article/details/9631787

刚学后缀自动机，还是有很多性质不是很了解……目前也就能做个模板题orz

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<cstdlib>
  4 #include<algorithm>
  5 
  6 using namespace std;
  7 
  8 #define N 2010
  9 #define MAXQ 10010
 10 
 11 struct Suffix_Automaton
 12 {
 13     int F[N << 1],ant,last,ch[N << 1][26],step[N << 1];
 14 
 15     void init()
 16     {
 17         last = ant = 1;
 18         memset(F,0,sizeof(F));
 19         memset(ch,0,sizeof(ch));
 20         memset(step,0,sizeof(step));
 21     }
 22 
 23     void ins(int x)
 24     {
 25         int t = ++ant, pa = last;
 26         step[t] = step[last] + 1;
 27         last = t;
 28         for( ; pa && !ch[pa][x]; pa = F[pa] )
 29             ch[pa][x] = t;
 30         if( pa == 0 ) F[t] = 1;
 31         else if( step[pa] + 1 == step[ ch[pa][x] ] )
 32             F[t] = ch[pa][x];
 33         else
 34         {
 35             int nq = ++ant, q = ch[pa][x];
 36             memcpy( ch[nq], ch[q], sizeof(ch[nq]) );
 37             step[nq] = step[pa] + 1;
 38             F[nq] = F[q];
 39             F[q] = F[t] = nq;
 40             for( ; pa && ch[pa][x] == q; pa = F[pa] )
 41                 ch[pa][x] = nq;
 42         }
 43     }
 44 };
 45 //以上为后缀自动机模板
 46 
 47 struct node
 48 {
 49     int l, r;
 50     int id;
 51 };
 52 
 53 node qry[MAXQ];
 54 char str[2010];
 55 int ans[MAXQ];
 56 Suffix_Automaton SAM;
 57 
 58 bool cmp( node a, node b )
 59 {
 60     if ( a.l == b.l ) return a.r < b.r;
 61     return a.l < b.l;
 62 }
 63 
 64 int main()
 65 {
 66     int T;
 67     scanf( "%d", &T );
 68     while ( T-- )
 69     {
 70         scanf( "%s", &str[1] );
 71         int Q;
 72         scanf( "%d", &Q );
 73         for ( int i = 0; i < Q; ++i )
 74         {
 75             scanf("%d%d", &qry[i].l, &qry[i].r );
 76             qry[i].id = i;
 77         }
 78         sort( qry, qry + Q, cmp );
 79 
 80         int preL = qry[0].l;
 81         SAM.init();
 82         int j = preL;
 83         for ( int i = 0; i < Q; ++i )
 84         {
 85             if ( qry[i].l == preL )
 86             {
 87                 while ( j <= qry[i].r )
 88                 {
 89                     SAM.ins( str[j] - 'a' );
 90                     ++j;
 91                 }
 92                 int tmp = 0;
 93                 for ( int k = SAM.ant; k > 0; --k )
 94                     tmp += SAM.step[k] - SAM.step[ SAM.F[k] ];
 95                 ans[ qry[i].id ] = tmp;
 96             }
 97             else
 98             {
 99                 preL = qry[i].l;
100                 j = qry[i].l;
101                 SAM.init();
102                 while ( j <= qry[i].r )
103                 {
104                     SAM.ins( str[j] - 'a' );
105                     ++j;
106                 }
107                 int tmp = 0;
108                 for ( int k = SAM.ant; k > 0; --k )
109                     tmp += SAM.step[k] - SAM.step[ SAM.F[k] ];
110                 ans[ qry[i].id ] = tmp;
111             }
112         }
113 
114         for ( int i = 0; i < Q; ++i )
115         printf( "%d
", ans[i] );
116     }
117     return 0;
118 }

推荐资料：

http://www.neroysq.com/?p=76

http://fanhq666.blog.163.com/blog/static/8194342620123352232937/

http://hi.baidu.com/myidea/item/142c5cd45901a51820e25039

http://blog.sina.com.cn/s/blog_70811e1a01014dkz.html