首页 > 代码库 > [hdu 4622]Reincarnation

[hdu 4622]Reincarnation

2024-07-17 15:06:42   214人阅读

这道题是妥妥的后缀自动机裸题

学了后缀自动机后，我居然感觉这尼玛果然还是后缀数组最难了有木有！

后缀自动机我的理解就是一个动态的存后缀的 AC 自动机

以为后缀的特殊性，我们可以在上一次插入的节点后直接插入新的节点，然后沿着 fail(pre) 指针把一些该更新的更新掉即可

果然是好写好用喵~

 

如何统计 [i..j] 的不同子串数呢？我们注意到每个节点 step 就是根到该节点的最长路径的长度

也就是以该节点结尾的后缀的最长长度

p->step-p->fail->step 就是节点 p 被插入后缀自动机后新增的以 p 为结尾的子串数量

这样一来题目就没有任何压力了有不有喵~

 

  1 #include <cstdio>  2 #include <cstring>  3 const int sizeOfString=2048;  4 const int sizeOfMemory=1000000;  5 const int sizeOfType=26;  6   7 namespace IOspace  8 {  9     inline int getint() 10     { 11         register int num=0; 12         register char ch; 13         do ch=getchar(); while (ch<‘0‘ || ch>‘9‘); 14         do num=num*10+ch-‘0‘, ch=getchar(); while (ch>=‘0‘ && ch<=‘9‘); 15         return num; 16     } 17     inline void putint(int num, char ch=‘\n‘) 18     { 19         char stack[10]; 20         register int top=0; 21         for ( ;num;num/=10) stack[++top]=num%10+‘0‘; 22         for ( ;top;top--) putchar(stack[top]); 23         if (ch) putchar(ch); 24     } 25 } 26 namespace suffixAutomaton 27 { 28     struct node 29     { 30         int step; 31         node * pre; 32         node * ch[sizeOfType]; 33         inline int calc() {return pre?step-pre->step:0;} 34     }; 35     int tot=0; 36     node memory[sizeOfMemory], * port; 37     node * dfa, * last; 38     inline node * newnode(node * t) 39     { 40         node * newt=port++; 41         newt->step=0; 42         if (t) newt->pre=t->pre, t->pre=newt, memcpy(newt->ch, t->ch, sizeof t->ch); 43         else newt->pre=NULL, memset(newt->ch, 0, sizeof newt->ch); 44         return newt; 45     } 46     inline void clear() {tot=0; port=memory; dfa=newnode(NULL); dfa->pre=dfa; last=dfa;} 47  48     inline int ord(char ch) {return ch-‘a‘;} 49     inline void insert(int w) 50     { 51         node * p=last, * newp=newnode(NULL); 52         newp->step=p->step+1; 53  54         for ( ;p->ch[w]==NULL;p=p->pre) p->ch[w]=newp; 55         if (p->ch[w]==newp) 56             newp->pre=dfa, tot+=newp->calc(); 57         else 58         { 59             node * q=p->ch[w]; 60             if (p->step+1==q->step) 61                 newp->pre=q, tot+=newp->calc(); 62             else 63             { 64                 tot-=p->calc()+q->calc(); 65                 node * newq=newnode(q); 66                 newq->step=p->step+1; 67                 newp->pre=newq; 68                 tot+=p->calc()+q->calc()+newp->calc()+newq->calc(); 69                 for ( ;p->ch[w]==q;p=p->pre) p->ch[w]=newq; 70             } 71         } 72  73         last=newp; 74     } 75 } 76  77 int T, n; 78 char s[sizeOfString]; 79 int ans[sizeOfString][sizeOfString]; 80  81 int main() 82 { 83     for (T=IOspace::getint();T;T--) 84     { 85         scanf("%s", s); 86         int len=strlen(s); 87         memset(ans, 0, sizeof ans); 88         for (int i=0;i<len;i++) 89         { 90             suffixAutomaton::clear(); 91             for (int j=i;j<len;j++) 92             { 93                 suffixAutomaton::insert(suffixAutomaton::ord(s[j])); 94                 ans[i][j]=suffixAutomaton::tot; 95             } 96         } 97         n=IOspace::getint(); 98         for (int i=1;i<=n;i++) 99         {100             int l=IOspace::getint()-1, r=IOspace::getint()-1;101             IOspace::putint(ans[l][r]);102         }103     }104 105     return 0;106 }
本傻装B系列

 


联系
我们