一、题目描述

P8715 [蓝桥杯 2020 省 AB2] 子串分值

二、问题简析

记录字符串 \(s\) 的 第 \(i\) 个字符 \(s_i\)（\(0\leq i<s.size\)）上一次出现的位置 \(pre_i\)、下一次出现的位置 \(nex_i\)，仅包含 \(s_i\) 的字串个数为 \((i - (pre_i + 1) + 1) * (nex_i - 1 - i + 1)\)，即 \((i-pre_i)*(nex_i-i)\)。只需要遍历所有的 \(s_i\)，将所有字串个数相加就是所求。

\(pre_i\)：因为字符串里只有 \(26\) 个小写字母，所以创建一个容量为 \(26\) 的临时数组 rec[26]，记录对应字母上次出现的下标（rec[0] 对应 a，rec[1] 对应 b，以此类推）。

• 1、因为要记录上一次出现的位置，所以要从左往右遍历，并更新相应的 rec[i]。
• 2、需要注意每个字母首次出现的 \(pre_i\)，因为是首次出现，所以下标从 \(0\) 至 \(i\) 的字母都可以是字串的开头，即 \(pre_i+1==0\)。因此，rec[26] 要初始化为 -1。

\(nex_i\)：与 \(pre_i\) 类似，也需要一个临时数组 rec[26]。不同点：

• 1、从右往左遍历，并更新相应字母的下标
• 2、rec[26] 初始化为 s.size，因为每个字母最后一次出现时，下标从 \(i\) 至 \(s.size-1\) 都可以作为字串的结尾，即 \(nex_i-1==s.size-1\)。

三、AC代码

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int MAX = 1e5 + 3;
int pre[MAX], nex[MAX], rec[30];
string s;

int main()
{
	#ifdef LOCAL
	freopen("test.in", "r", stdin);
	#endif
	
	cin >> s;
	int sSize = s.size();
	fill(rec, rec + 26, -1);
	for (int i = 0; i < sSize; i++)
	{
		pre[i] = rec[s[i] - 'a'];
		rec[s[i] - 'a'] = i;
	}
	fill(rec, rec + 26, sSize);
	for (int i = sSize - 1; i >= 0; i--)
	{
		nex[i] = rec[s[i] - 'a'];
		rec[s[i] - 'a'] = i;
	}
	
	ll ans = 0;
	for (int i = 0; i < sSize; i++)
	{
		ans += (i - pre[i]) * (nex[i] - i);
	}
	cout << ans << endl;
	
	return 0;
}

完