题意翻译

T组数据,每组数据一个字符串,求每个本质不同的子串在序列中出现次数的平方和。

输入输出样例

输入

4
aa
abcd
ccc
abcc

输出

5
10
14
12

说明/提示

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.

 

挺好一题,有挺多不同的思路切入。

 

先贴一个后缀数组+单调栈+考虑增量贡献的解法,题解是手写的大字报,挺妙的。

    struct SuffixArray{
            //略
    }SA;
           {
            scanf("%s",s);
		while (!S.empty()) S.pop();
		n=strlen(s)+1;
		for (int i=0;i<n-1;i++) a[i]=s[i];
		a[n-1]=0;
		SA.build_sa(256,n);
		SA.getHeight(n);
		int nn=n-1;
		ll ans=(ll)(nn+1)*nn/2;
		tot=0;
		for (int i=1;i<n;i++)
		{
			cnt=0;//cnt记录height小于等于当前值的数量
                        //stack满足单调栈性质,栈顶元素最大
			while (!S.empty())
			{
				ll val=S.top().first;
				ll C=S.top().second;
				if (val<height[i]) break;
				S.pop();
				tot-=val*C;//减去大于当前height的值带来的贡献
				cnt+=C;
			}
			tot=tot+height[i]*(cnt+1);
			ans=ans+2*tot;
			S.push(mp(height[i],cnt+1));
	        }
           cout<<ans<<endl;

0 条评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注