[数据结构与算法]题目 2572: 蓝桥杯2020年第十一届省赛真题-子串分值

题目

对于一个字符串S，我们定义S 的分值 f(S) 为S中恰好出现一次的字符个数。例如f (”aba”) = 1，f (”abc”) = 3, f (”aaa”) = 0。
现在给定一个字符串S[0…n-1]（长度为n），请你计算对于所有S的非空子串S[i…j](0 ≤ i ≤ j < n)， f (S[i… j]) 的和是多少。

输入
输入一行包含一个由小写字母组成的字符串S。

输出
输出一个整数表示答案。
样例输入

ababc

样例输出

21

提示
样例说明：

子串f值：

a     1
ab    2
aba   1
abab  0
ababc 1
 b    1
 ba   2
 bab  1
 babc 2
  a   1
  ab  2
  abc 3
   b  1
   bc 2
    c 1

对于20% 的评测用例，1 ≤ n ≤ 10；
对于40% 的评测用例，1 ≤ n ≤ 100；
对于50% 的评测用例，1 ≤ n ≤ 1000；
对于60% 的评测用例，1 ≤ n ≤ 10000；
对于所有评测用例，1 ≤ n ≤ 100000。

解题思路

本题的题意是，在给定的字符串当中取一个（连续的）子串，该子串当中只出现了一次的字母种类数，即为该子串的值；列举所有不重复的子串，输出它们的值之和。

最直接的方法是遍历，但显然数据量过大，会超时。故又想到了前缀和，只需遍历字符串一次，即可得到第i个下标之前，某个字母出现的次数，下面来寻找前缀和与答案之间的关系。下表是样例的前缀和：

答案由两部分组成，一部分是恰好前缀和为1的情况数目，它们是自己本身（单个字母）或者a[0]-a[i]（取到头）组成的子串；另一部分是截取一段子串a[i]-a[j]（i!=0且i!=j），使得某一字母的前缀和之差恰好为1（这意味着这一段当中该字母仅出现了一次，可以计入子串的数值）。

比如：对于上面的样例，具体而言，字母a对子串和的贡献是1*2+(2-1)*6=8。

代码

#include<stdio.h>
#include<string.h>
int acu[26][100001];//统计各个字母累加的个数
int num[26][100001];
int main()
{
	char a[100001];//字符串长度
	scanf("%s",a);
	int i,j,lena = strlen(a);
	long int temp,sum = 0;
	for (i=0;i<lena;i++)
	{
	    acu[a[i]-97][i]++;
	    for (j=0;j<26;j++)
	    {
	        if (i!=0)
        	    acu[j][i]+=acu[j][i-1];
        	num[j][acu[j][i]]++;//累计数目为acu的值的数目加一
	    }
	}
	for (i=1;i<lena;i++)
	{
	    for (j=0;j<26;j++)
	    {
	        temp = num[j][i]*num[j][i-1];
	        sum+=temp;
            if (i==1)
                sum+=num[j][1];
	    }
	}
	printf("%ld",sum);
	return 0;
}