蓝桥杯：子串分值

子串分值【模拟】

题目描述

对于一个字符串 S，我们定义 S 的分值 f(S) 为 SS 中恰好出现一次的字符个数。例如 f(aba)=1，f(abc)=3,f(aaa)=0。

现在给定一个字符串 S_0⋯n−1（长度为 n，1≤n≤10⁵），请你计算对于所有 S 的非空子串 S_i⋯j(0≤i≤j<n)，f(S_i⋯j) 的和是多少。

输入描述

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

输出描述

输出一个整数表示答案。

输入输出样例

示例

输入

ababc
1

输出

21
1

样例说明：

子串   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

思路：

这道题用暴力法只能得到一般的分数，运行会超时，所以只能计算每个字母的贡献值，这样可以节约运行时间。
要想计算贡献值，对每一个字母 x[i]，找到前一个相同的字母下标 pre[i]，后一个相同字母的下标 next[i]，然后用贡献值的计算公式
(i-pre[i])*(next[i]-i) (这个公式计算的是一个字母的贡献值，将所有的字母的贡献值加在一起就是结果了)

​ 这个算法是计算字符串中每个字符的贡献值即影响因子，将贡献值累加就得到了结果。那么该如何来计算每个字符的贡献值呢？
所谓贡献值，即该字符能够影响到的子串个数，就比如
​ 0 1 2 3 4 5
​ b a c b e b
表格中的3号b能够影响多少个子串呢？
列举一下有：acbe,acb,cbe,cb,b,be共有6个（这些子串的f值都因为b增加了1，而 bacb这个子串不会因为3号b增加f值）.
那么如何用数学的方法计算出来贡献值呢？
这些子串的起点可以为1、2、3，终点可以为3、4，即（3-0)(5-3） = 6
其中 0 是 3号 b往左遇到的第一个b的标号，而 5是 3号 b往右遇到的第一个 b的标号。
！！！！！推论：一个字符（位置为i）的影响范围由其往左边遍历遇到的第一个相同字符（位置为left）和
​ 其往右边遍历遇到的第一个相同字符（位置为right）所决定。其贡献值为（i - left）*（right - i）
乘法原理 O ( N )：

解题思路：

1、统计每个字母在仅出现一次的情况下，能被多少子串所包含；
2、用 pre[i] 记录第 i 个字母上一次出现的位置，用 next[i] 记录第 i 个字母下一次出现的位置；
3、那么往左最多能延伸到 pre[i] + 1，其到第 i 个字母一共有 i - pre[i] 个字母；
4、同理往右最多能延伸到 next[i] - 1，其到第 i 个字母一共有 next[i] - i 个字母；
5、二者相乘，就是该字母被不同子串所包含的总次数；

代码：

#include
#include
#define N 100002
int main()
{
	char x[N];
	int pre[N];     //存放该位置的前一个相同字母的位置 
	int next[N];    //放该位置的后一个相同字母的位置 
	int late[27];   //储存该字母的索引 
	int sum=0;
	scanf("%s",x);
	int len=strlen(x);
	//求该字母的前一个相同的字母的位置 
	for(int i=0;i<=26;i++)
		late[i]=-1;   //初始化每个字母的前序索引为 x 开始的前一个位置，也就是 -1 
	for(int i=0;i<len;i++)
	{   //找到每个位置的前一个相同字母的位置 
		int m=x[i]-'a';
		pre[i]=late[m];
		late[m]=i;
	}
	//求该字母的后一个相同的字母的位置 
	for(int i=0;i<=26;i++)
		late[i]=len;   //初始化每个字母的后序索引为 x 结束的后一个位置，也就是 n 
	for(int i=len-1;i>=0;i--)
	{   //找到每个位置的后一个相同字母的位置
		int m=x[i]-'a';
		next[i]=late[m];
		late[m]=i;
	}
	//累加每个字母的贡献值 
	for(int i=0;i<len;i++)
		sum+=(i-pre[i])*(next[i]-i);
	
	printf("%d",sum);
	return 0;
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37