蓝桥杯 历届试题 子串分值【第十一届】【省赛】【A组】dfs和尺取法 C++

乘法原理 O ( N ) ：
解题思路：
统计每个字母在仅出现一次的情况下，能被多少子串所包含；
用 pre[i] 记录第 i 个字母上一次出现的位置，用 next[i] 记录第 i 个字母下一次出现的位置；
那么对于第i个字母，

其往左最多能延伸到 pre[i] + 1，到第 i 个字母一共有 i - pre[i] 个字母；
同理往右最多能延伸到 next[i] - 1，到第 i 个字母一共有 next[i] - i 个字母；
二者相乘，就是该字母被不同子串所包含的总次数；
再换种说法分析，即对于字符串中的每个字符，我们可以考虑它对答案的贡献度，即 它 所能在的所有的字符子串中，它是唯一的个数，设某个字符位置位a,和它相同的前一个字符位置为b，和它相同的后一个字符位置为c，那么他的贡献度为（a-b）*（c-a）,其中a-b种取法是在a和b之间有a-b-1个字母，（不包括端点，因为端点是a和b，a必取，b必不取，所以不算在取法中）可以取0到a-b-1个字符。

同理，a和c之间可以取0到c-a-1个字符，即c-a种方法。

两者相乘即是a作为某字串中唯一的字符时的贡献。

运用了简单的计数原理。

为了加快时间，我们预处理每个字符的上一个位置和下一个位置。

#include
#define ll long long
using namespace std;
const int N = 1e5 + 5, M = 1e5 + 5;
int pre[N], ne[N], ans;//pre[i]的值即 对于下标为i的字符的前一个相同字符的位置
int last[30];//记录某字母最后一次出现的位置 
int main() {
	string s;
	getline(cin, s);
	int len = s.length();
	memset(last, -1, sizeof(last));//前面没有就是-1，这样0-（-1）是1 
	for (int i = 0; i < len; i++) {
		pre[i] = last[s[i] - 'a'];//每个字符-'a'相当于得到它和'a'的距离，可以作为独特下标索引
		//因为循环会不断的更新pre和last数组，所以pre[i]最终存的就是
		//前面一个和自己相同的字符的下标，即是上一次更新后的最后的此字符位置
		last[s[i] - 'a'] = i; //更新s[i]字符最后一次出现的位置
	}
	for (int i = 0; i < 26; i++)	last[i] = len;//如果后面没有就是len。

因为最多只能从最后一位选
	//为什么要倒着推，因为我们要知道x字符的下一个位置，必然需要提前知道他后面的 
	for (int i = len - 1; i >= 0; i--) {
		ne[i] = last[s[i] - 'a'];//与pre的更新同理，倒着更新使得ne[i]存着对于i下标字符而言最近的下一个字符的下标
		last[s[i] - 'a'] = i; //更新s[i]字符最后一次出现的位置
	}
 
	for (int i = 0; i < len; i++)
		ans += (i - pre[i]) * (ne[i] - i);
	//i点的上一个相同字符距离x，下一个位y， 
	//左边可以取x种（1-x），右边y种，共x*y 
	cout << ans;
	return 0;
}