由于子串个数是2^(n-1),所以肯定不能从子串入手,不妨从每个字母入手
定义l是字母q左侧离它最近的q的位置,r是右侧离它最近的q的位置,则在(l,r)区间内必然只有一个q,所以对于(l,r)区间内的所有子串(包含q),q对它们的分值都贡献了1。这便是称作贡献法的含义吧。
由于统计的是每个字母的贡献,所以这种统计方式一定是不重不漏的
#include<bits/stdc++.h>
using namespace std;
const int N=100010;
typedef long long LL;
typedef pair<int,int> PII;
int l[N],r[N];//每个字母左/右第一个相同字母的位置
int p[128];
int main(){
string s;
cin>>s;
int n=s.size();
for(int i=0;i<128;i++) p[i]=-1;
for(int i=0;i<n;i++){
l[i]=p[s[i]];
p[s[i]]=i;
}
for(int i=0;i<128;i++) p[i]=n;
for(int i=n-1;i>=0;i--){
r[i]=p[s[i]];
p[s[i]]=i;
}
LL res=0;
for(int i=0;i<n;i++) res+=(LL)(i-l[i])*(r[i]-i);
cout<<res;
return 0;
}