Helvetic Coding Contest 2017 online mirror I

Helvetic Coding Contest 2017 online mirror I - Fake News (hard)

阅读量：6123 次

发布时间：2019-06-21

本文共 3499 字，大约阅读时间需要 11 分钟。

Now that you have proposed a fake post for the HC2 Facebook page, Heidi wants to measure the quality of the post before actually posting it. She recently came across a (possibly fake) article about the impact of fractal structure on multimedia messages and she is now trying to measure the self-similarity of the message, which is defined as

$\text{[math]}$

where the sum is over all nonempty strings p and $\text{[math]}$ is the number of occurences of p in s as a substring. (Note that the sum is infinite, but it only has a finite number of nonzero summands.)

Heidi refuses to do anything else until she knows how to calculate this self-similarity. Could you please help her? (If you would like to instead convince Heidi that a finite string cannot be a fractal anyway – do not bother, we have already tried.)

Input

The input starts with a line indicating the number of test cases T (1 ≤ T ≤ 10). After that, T test cases follow, each of which consists of one line containing a string s (1 ≤ |s| ≤ 100 000) composed of lowercase letters (a-z).

Output

Output T lines, every line containing one number – the answer to the corresponding test case.

Example

input

4 aa abcd ccc abcc

output

5 10 14 12

Note

A string s contains another string p as a substring if p is a contiguous subsequence of s. For example, ab is a substring of cab but not of acb.

题目大意：求一个字符串所有子串的出现次数平方和

惊了，我会Hard但是不会做normal

这个，参考一下弦论的话就是SAM裸题吧

SAM的每个状态代表了一些子串，它们的出现次数是就是R集合的大小，而子串的个数就是maxl-minl+1

求出SAM，求出每个状态的R集合大小s，以及maxl和minl

最终的答案就是 $ \sum (maxl-minl+1)s^2 $

R集合不是要拓扑排序么，事实上直接按照MAXL基数排序即可，从黄学长那学来的奇技淫巧

1 #include 
         
            2 #include 
          
             3 #include 
           
              4 #include 
            
               5 #include 
             
                6 #include 
              
                7 #include 
               
                 8 #include 
                 9 #include 
                 
                   10 #include 
                  
                    11 #include 
                   
                     12 #include 
                    
                      13 #include 
                     
                       14 #define eps 1e-7 15 #define INF 0x3f3f3f3f 16 #define MOD 1000000007 17 #define rep0(j,n) for(int j=0;j
                      
                       nxt) 24 #define max(a,b) (a>b?a:b) 25 #define min(a,b) (a
                       
                        c,0,sizeof(p->c)); 59 p->fa=NULL; 60 p->maxl=maxl; 61 p->cnt=p->r=0; 62 return p; 63 } 64 SAM(){ 65 cnt=0; 66 root = newnode(0); 67 last=root; 68 } 69 void append(int w){ 70 cond *p=last; 71 cond *np=newnode(p->maxl+1); 72 np->r=1; 73 while(p&&!p->c[w]) p->c[w]=np,p=p->fa; 74 if(!p) np->fa=root; 75 else{ 76 cond *q=p->c[w]; 77 if(q->maxl==p->maxl+1) np->fa=q; 78 else{ 79 cond *nq = newnode(p->maxl+1); 80 memcpy(nq->c,q->c,sizeof(q->c)); 81 nq->fa=q->fa; 82 q->fa=nq;np->fa=nq; 83 while(p&&p->c[w]==q) p->c[w]=nq,p=p->fa; 84 } 85 } 86 last=np; 87 } 88 ll calc(){ 89 memset(ct,0,sizeof(ct)); 90 ll ans=0; 91 rep1(i,cnt-1) ct[mp[i].maxl]++; 92 rep1(i,MAXINT-1) ct[i]+=ct[i-1]; 93 rep1(i,cnt-1) srt[ct[mp[i].maxl]--]=i; 94 for(int i=cnt-1;i>=1;i--) { 95 mp[srt[i]].cnt+=mp[srt[i]].r; 96 mp[srt[i]].fa->cnt+=mp[srt[i]].cnt; 97 } 98 rep1(i,cnt-1) ans+=(ll)(mp[i].maxl-mp[i].fa->maxl)*mp[i].cnt*mp[i].cnt; 99 cnt=0;100 root = newnode(0);101 last=root;102 return ans;103 }104 }sam;105 void get_input();106 void work();107 int main() {108 int T=read();109 while(T--){110 get_input();111 work(); 112 }113 return 0;114 }115 void work(){116 printf("%lld\n",sam.calc());117 }118 void get_input(){119 scanf("%s",s);120 int l =strlen(s);121 rep0(i,l) sam.append(s[i]-'a');122 }

转载于:https://www.cnblogs.com/LoveYayoi/p/6938570.html

你可能感兴趣的文章