本文主要是介绍HDU 4622 Reincarnation(SAM 后缀自动机 求子串的不同子串个数)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4622
这个题目开始是用后缀数组来做的，但是这个题目对后缀数组时间卡的很紧，后来看解题报告说是用后缀自动机搞定的，想想也是CLJ出题怎么会没有后缀
自动机呢
其实这个题目字符串长度不算长2000，但是查询可以达到10000次，如果每次查询都重新建立后缀自动机来计算不同子串的个数的话会超时，但是考虑到后
缀自动机的构造过程的一个在线的，所以我们就考虑能不能先把要查询的区间排序，然后按照左边界排序，左边界相同的按照右边界从小到达排序，这样，
在构造后缀自动机的时候现在的就可以在先前的基础上构造了（一定是后一个的l和前一个的l相等，如果不相等就重新构造），这样我们最多构造两千次
这样复杂度就够了！
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define maxn 2100
struct point
{point *father,*next[26];int val;
}po[maxn*3],*root,*tail;
int tot,len,ans[110000];
char str[maxn];
struct query
{int l,r;int num;
}rec[11000];
void add(int c,int l)
{point *p=tail,*np=&po[tot++];np->val=l;while(p&&p->next[c]==NULL)p->next[c]=np,p=p->father;if(p==NULL) np->father=root;else{point *q=p->next[c];if(p->val+1==q->val) np->father=q;else{point *nq=&po[tot++];*nq=*q;nq->val=p->val+1;np->father=q->father=nq;while(p&&p->next[c]==q) p->next[c]=nq,p=p->father;}}tail=np;
}
bool cmp(const query &a,const query &b)
{if(a.l != b.l)return a.l < b.l;if(a.r !=b.r)return a.r < b.r;return a.num < b.num;
}
int start()
{memset(po,0,sizeof(po));len=1,tot=1;root=tail=&po[0];return 0;
}
int find_ans()//后缀自动机求不同子串个数
{int i,j,ans=0;for(i=tot-1;i>0;i--)ans+=po[i].val-po[i].father->val;return ans;
}
int main()
{int t,i,j,k,n;scanf("%d",&t);while(t--){scanf("%s",str+1);scanf("%d",&n);for(i=1;i<=n;i++){scanf("%d%d",&rec[i].l,&rec[i].r);rec[i].num=i;}sort(rec+1,rec+1+n,cmp);start();j=1;for(i=1;i<=n;i++){if(i==1 || rec[i].l==rec[i-1].l){for(j;j<=rec[i].r;j++)add(str[j]-'a',len++);}else{start();for(j=rec[i].l;j<=rec[i].r;j++)add(str[j]-'a',len++);}ans[rec[i].num]=find_ans();}for(i=1;i<=n;i++)printf("%d\n",ans[i]);}return 0;
}
这篇关于HDU 4622 Reincarnation(SAM 后缀自动机 求子串的不同子串个数)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
