首页 > 代码库 > [hdu 4416]Good Article Good sentence

[hdu 4416]Good Article Good sentence

2024-07-17 20:20:03   216人阅读

最近几天一直在做有关后缀自动机的题目

感觉似乎对后缀自动机越来越了解了呢！喵~

 

这题还是让我受益颇多的，首先搞一个后缀自动机是妥妥的了

可是搞完之后呢？

我们来观察 step 这个变量，每个节点的 step 是从根节点到此节点所经过的最长步数

那么也就是以该点为结尾的最长的后缀长度

如何统计不被 Bi 串包含的子串呢？

其实很简单，维护每个节点所能匹配的最长的字符串长度

然后 节点->step-max(该节点所能匹配的最长的字符串长度, 节点->fail->step) 就是答案了

因为 S[0..节点->step-1] 必是原串的一个后缀，而 节点所能匹配的最长字符串长度 d 说明 S[节点->step-d..节点->step-1] 是出现在了某个 Bi 串中的

只不过把每个串在自动机上跑一遍并不能得到每个节点所能匹配的最长长度

因为当该节点被匹配时，该结点的 fail 指针所指向的节点也必然被匹配到了

我们需要一个拓扑排序，按拓扑序来更新答案，并同时更新每个节点的 fail 指针指向的点的匹配长度

教练，我不想写拓扑排序~

我才不会说按 step 从大到小的顺序就是拓扑序呢喵~

 

namespace 写写被 hdu 怒骂 TLE TAT ，这是多么痛的领悟……

  1 #include <cstdio>  2 #include <cstring>  3 #include <algorithm>  4 #define ord(ch) ((ch)-‘a‘)  5 typedef long long llint;  6 const int sizeOfString=550005;  7 const int sizeOfMemory=550005<<1;  8 const int sizeOfType=26;  9  10 inline int max(int x, int y) {return x>y?x:y;} 11  12 struct node 13 { 14     int step; 15     int same; 16     node * fail; 17     node * ch[sizeOfType]; 18 }; 19 node memory[sizeOfMemory]; int port; 20 node * dfa=memory, * last; 21 inline node * newnode(node * t=NULL) 22 { 23     node * newt=memory+(port++); 24     newt->step=0; 25     newt->same=0; 26     if (t) newt->fail=t->fail, t->fail=newt, memcpy(newt->ch, t->ch, sizeof t->ch); 27     else newt->fail=NULL, memset(newt->ch, 0, sizeof newt->ch); 28     return newt; 29 } 30 inline void insert(int w) 31 { 32     node * p=last, * newp=newnode(); 33     newp->step=p->step+1; 34  35     for ( ;p->ch[w]==NULL;p=p->fail) p->ch[w]=newp; 36     if (p->ch[w]==newp) 37         newp->fail=dfa; 38     else 39     { 40         node * q=p->ch[w]; 41         if (q->step==p->step+1) 42             newp->fail=q; 43         else 44         { 45             node * newq=newnode(q); 46             newq->step=p->step+1; 47             newp->fail=newq; 48             for ( ;p->ch[w]==q;p=p->fail) p->ch[w]=newq; 49         } 50     } 51  52     last=newp; 53 } 54 inline void search(char * s) 55 { 56     int len=strlen(s); 57     int tot=0; 58     node * t=dfa; 59     for (int i=0;i<len;i++) 60     { 61         int w=ord(s[i]); 62         if (t->ch[w]) 63         { 64             t=t->ch[w]; 65             t->same=max(t->same, ++tot); 66         } 67         else 68         { 69             node * j; 70             for (j=t->fail;j!=dfa && !j->ch[w];j=j->fail); 71             if (j->ch[w]) 72             { 73                 t=j->ch[w]; 74                 t->same=max(t->same, tot=(j->step+1)); 75             } 76             else 77             { 78                 t=dfa; 79                 tot=0; 80             } 81         } 82     } 83 } 84 inline llint calc(int len) 85 { 86     static node * p[sizeOfMemory]; 87     static int cnt[sizeOfString]; 88     llint ret=0; 89  90     memset(cnt, 0, sizeof(cnt)); 91     for (int i=0;i<port;i++) cnt[dfa[i].step]++; 92     for (int i=1;i<=len;i++) cnt[i]+=cnt[i-1]; 93     for (int i=0;i<port;i++) p[--cnt[dfa[i].step]]=&dfa[i]; 94     for (int i=port-1;i>0;i--) 95     { 96         p[i]->fail->same=max(p[i]->fail->same, p[i]->same); 97         if (p[i]->same<p[i]->step) 98             ret+=p[i]->step-max(p[i]->same, p[i]->fail->step); 99     }100 101     return ret;102 }103 104 int T, n;105 char str[sizeOfString], s[sizeOfString];106 107 int main()108 {109     int cases=0;110 111     for (scanf("%d", &T);T;T--)112     {113         scanf("%d", &n);114         scanf("%s", str);115         port=0; dfa=newnode(); dfa->fail=dfa; last=dfa;116         int len=strlen(str);117         for (int i=0;i<len;i++)118             insert(ord(str[i]));119         for (int i=1;i<=n;i++)120         {121             scanf("%s", s);122             search(s);123         }124         printf("Case %d: %I64d\n", ++cases, calc(len));125     }126 127     return 0;128 }
本傻装B不成反被艹系列

 


联系
我们