BZOJ3238: [Ahoi2013]差异(后缀数组)

Description

Input

一行,一个字符串S

Output

一行,一个整数,表示所求值

Sample Input

cacao

Sample Output

54

解题思路:

看到lcp,想到了height数组,没错,这道题是一道后缀数组题。

前面那两项好像可以累和,值为(len-1)*len*(len+1)/2

就剩sigma(lcp)了。

想到了单调栈直接累和发现WA了,非常尴尬。

最后知道好像漏了点什么,就是说之前的height不可以说弹栈了就要遗弃,那是会漏解的。

要重复累加。也就是用dp数组来维护贡献,每次弹栈后累加。

你不会怕我加重吧,可以证明,弹栈只会在一个阶段停下,而之前的值在最终贡献中体现。

代码:

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 typedef long long lnt;
 5 int sa[1000000];
 6 int rnk[1000000];
 7 int has[1000000];
 8 int tmr[1000000];
 9 int hgt[1000000];
10 char str[1000000];
11 char ln[1000000];
12 int stack[1000000];
13 lnt dp[1000000];
14 int top;
15 int len;
16 int cnt;
17 lnt ans;
18 bool Same(int a,int b,int l)
19 {
20     if(a+l>len||b+l>len)
21         return false;
22     return (rnk[a]==rnk[b])&&(rnk[a+l]==rnk[b+l]);
23 }
24 int main()
25 {
26     scanf("%s",str+1);
27     len=strlen(str+1);
28     for(int i=1;i<=len;i++)
29         has[str[i]]++;
30     for(int i=0;i<128;i++)
31         if(has[i])
32             tmr[i]=++cnt;
33     for(int i=1;i<128;i++)
34         has[i]+=has[i-1];
35     for(int i=1;i<=len;i++)
36     {
37         sa[has[str[i]]--]=i;
38         rnk[i]=tmr[str[i]];
39     }
40     for(int k=1;cnt!=len;k<<=1)
41     {
42         cnt=0;
43         for(int i=0;i<=len;i++)
44             has[i]=0;
45         for(int i=1;i<=len;i++)
46             has[rnk[i]]++;
47         for(int i=1;i<=len;i++)
48             has[i]+=has[i-1];
49         for(int i=len;i;i--)
50             if(sa[i]>k)
51                 tmr[sa[i]-k]=has[rnk[sa[i]-k]]--;
52         for(int i=1;i<=k;i++)
53             tmr[len-i+1]=has[rnk[len-i+1]]--;
54         for(int i=1;i<=len;i++)
55             sa[tmr[i]]=i;
56         for(int i=1;i<=len;i++)
57             if(Same(sa[i],sa[i-1],k))
58                 tmr[sa[i]]=cnt;
59             else
60                 tmr[sa[i]]=++cnt;
61         for(int i=1;i<=len;i++)
62             rnk[i]=tmr[i];
63     }
64     hgt[1]=0;
65     for(int i=1;i<=len;i++)
66     {
67         if(rnk[i]==1)
68             continue;
69         int j=std::max(1,hgt[rnk[i-1]]-1);
70         while(str[i+j-1]==str[sa[rnk[i]-1]+j-1])
71             hgt[rnk[i]]=j++;
72     }
73     stack[0]=0;
74     for(int i=1;i<=len;i++)
75     {
76         while(top&&hgt[stack[top]]>hgt[i])
77             top--;
78         dp[i]=(lnt)(i-stack[top])*(lnt)(hgt[i])+dp[stack[top]];
79         ans+=dp[i];
80         stack[++top]=i;
81     }
82     ans<<=1;
83     printf("%lld
",(lnt)(len-1)*(lnt)(len+1)*(lnt)(len)/2-ans);
84     return 0;
85 }
原文地址:https://www.cnblogs.com/blog-Dr-J/p/10014011.html