利用贡献值，每一个字符受到前后相同字符的影响

解题思路:贡献值

注意事项:初始化num[i] = -1

参考代码:

#include<stdio.h>

#include<string.h>

int main()

{

    char s[100010];

    gets(s);

    int dp[100010];

    int len = strlen(s);

    int num[26];

    for(int i = 0; i < len; i++)    num[i] = -1;

    for(int i = 0; i < len; i++){

        if(num[s[i]-'a'] == -1){    //首次出现

            int j = i+1;

            for(j = i+1; j < len; j++){

                if(s[i] == s[j])

                    break;

            }

            dp[i] = (i+1) * (j-i);

        }

        else{

            int j = i+1;

            for(j = i+1; j < len; j++){

                if(s[i] == s[j])

                    break;

            }

            dp[i] = (i-num[s[i] - 'a']) * (j-i);

        }

        num[s[i] - 'a'] = i;

    }

    int sum = 0;

    for(int i = 0; i < len; i++)

        sum += dp[i];

    printf("%d",sum);

}