子串分值（贡献分析法）

解题思路:

贡献法：前面的a为l,中间的a为p，后面的a为r,中间的a的贡献值就为 (p-l)*(r-p)

如果前面没有a，则l=0;若末尾没有a，则r=n+1;

如：0abcabca

第一个a的下标为1，中间a的下表为4，后面a的下标为7，则中间a的贡献值为（4-1）*（7-4）=9；

对于中间的字符a,贡献情况有以下9种：

bca   

bcab  

bcabc

ca

cab

cabc

a

ab

abc

将字符串中每个字符的贡献值累加即为答案

注意事项:

参考代码:

#include

#define int long long

using namespace std;

string s;

int n,ans;

signed main()

{

cin>>s;

n=s.length();

s='0'+s;

for(int i=1;i<=n;i++)

{

int l=0,r=n+1;

for(int x=i;x>=1;x--){//寻找l值

if(s[x]==s[i]&&x!=i)

{

l=x;

break;

}

}

for(int y=i+1;y<=n;y++)//寻找r值

{

if(s[y]==s[i]&&y!=i)

{

r=y;

break;

}

}

ans+=(i-l)*(r-i);

}

cout<<ans;

return 0;

}