HDU 4622 求解区间字符串中的不同子串的个数

题目大意：

给定一个长度<2000的串，再给最多可达10000的询问区间，求解区间字符串中的不同子串的个数

这里先考虑求解一整个字符串的所有不同子串的方法

对于后缀自动机来说，我们动态往里添加一个字符，每次添加一个字符进去，我们只考虑那个生成的长度为当前长度的后缀自动机的节点

那么这个节点可接收的字符串的个数就是( p->l - p->f->l )，也就是以当前点为最后节点所能得到的与之前不重复的子串的个数

那么这个问题就很好解决了，共2000个位置，以每一个位置为起点构建一次后缀自动机，一直构建到最后一个字符，过程中不断记录所能得到的子串个数

把这个个数动态保存到f[][]数组中

那么打好了表，最后询问的时候，直接访问这个f[][]即可

 #include <cstdio>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 #define N 2005

 #define M 26

 struct SamNode{

     SamNode *son[M] , *f;

     int l;

     void init(){

         for(int i= ; i<M ; i++) son[i] = NULL;

         f=NULL , l=;

     }

 }sam[N<<] , *root , *last;

 int cnt , f[N][N] , ret;

 char s[N] ;

 void init(){

     sam[].init();

     root = last = &sam[cnt=];

 }

 void add(int x)

 {

     SamNode *p = &sam[++cnt] , *jp=last;

     p->init();

     p->l = jp->l+;

     last = p;

     for(; jp&&!jp->son[x] ; jp=jp->f) jp->son[x] = p;

     if(!jp) p->f = root;

     else{

         if(jp->l+ == jp->son[x]->l) p->f = jp->son[x];

         else{

             SamNode *r = &sam[++cnt] , *q = jp->son[x];

             r->init();

             *r = *q; r->l = jp->l+;

             p->f = q->f = r;

             for( ; jp&&jp->son[x]==q ; jp=jp->f) jp->son[x] = r;

         }

     }

     ret += p->l-(p->f->l);

 }

 void solve()

 {

     int len = strlen(s);

     for(int i= ; i<len ; i++){

         ret = ;

         init();

         for(int j=i ; j<len ; j++){

             add(s[j]-'a');

             f[i][j] = ret;

         }

     }

 }

 int main()

 {

   //  freopen("a.in" , "r" , stdin);

     int T;

     scanf("%d" , &T);

     while(T--)

     {

         scanf("%s", s);

         int m , l , r;

         scanf("%d" , &m);

         solve();

         while(m--){

             scanf("%d%d" , &l , &r);

             printf("%d\n" , f[l-][r-]);

         }

     }

     return ;

 }

HDU 4622 求解区间字符串中的不同子串的个数的相关教程结束。