蓝桥杯-子串分值和

题目描述

对于一个字符串 S，我们定义 S 的分值 f(S) 为 S 中出现的不同的字符个数。

例如 f(“aba”)=2，f(“abc”)=3,f(“aaa”)=1 。

现在给定一个字符串 S[0..n−1]（长度为 n），请你计算对于所有 S 的非空子串 Si..j，f(S[i..j]) 的和是多少。

子串

首先了解什么是子串,一个字符串 s 被称作另一个字符串 S 的子串，表示S=XsY。

例如abcc的子串有

{

空串

b ab

c bc abc

c cc bcc abcc

}

为什么会有两个子串c?

第一个子串c前面是_ab_后面是_c_，第二个子串c前面是_abc_后面是空，都满足定义！

思路

我们可以用状态转移的方法来思考，状态的定义是当前字符串所有子串的集合(例如:ab,当前字符串子串集合为{a,b,ab,空串})，当新来一个字母b接到字符串后方时，子串集合可以由两部分转移

老的子串集合直接转移,即{a,b,ab,空串}
新生成的子串,这部分子串可分为两部分

新来的字母单独做为一个子串,即字母{b}
可以将新字母直接接在旧子串后面形成新子串,即直接接在前一个字母b后面形成{bb,abb}

所以当前状态abb所表示的新集合为:接在后面的集合+新字母单独做子串集合+旧集合，即{bb,abb}+{b}+{a,b,ab,空串}={a,b,ab,空串b,bb,abb}

我们再来看看在转移过程中,子串数值的变化,仍然以上面的ab新添加b为例子,设旧子串集合{a,b,ab,空串}的总数值为sum0,新子串集合的总数值为x,最终形成的子串集合为sum1,所以

sum1=sum0+x -> sum = sum + x

递推公式已经推出,我们来看看这个x的数值是怎样变化的,{bb,abb}它是由旧集合中以最后一个字母结尾的子串{b,ab}再加上新字符b形成的,根据题目的定义如果新添加的字符前面已经存在，那么数值不变仍然为前面的子串的数值，反之则在前面子串基础上加上新字符的数值即1.回到x上来,从{b,ab}到{bb,abb},我们设{a,ab}数值为x0,{bb,abb}数值为x1,可以知道x1=x0+增量c,增量c是由新加字符决定的，也就是前面有多少个不含新字符的子串数量,这里的增量为0，因为b,ab都含有新加字符b.现在x的递推公式也得到了,最后别忘了新来的字母单独做为一个子串,即字母{b}。

x1 = x0 + 增量 + 1

最后我们可以开一个数组st[i]来记录当前状态不含某个字符i的子串数量,当新加一个字符时，我们直接查询即可得到增量,添加完字符后我们对st数组进行更新即可

x = x + st[i] + 1

AC代码

#include <iostream>
#include <cstring>
using namespace std;
char chs[100005];   //用来存储字符串
int st[30]; //存储不包含i字符的子串数
void update(char ch){   //在旧字符串后面加上新字母后，更新st数组
    int aim = ch-'a';   //计算索引,a对应下标0，b对应1以此类推
    st[aim] = 0;    //由于在可加的所有子串末尾新加了字母ch，所以前面的所有子串都不包含新加的字母
    for(int i = 0;i<30;i++){    //遍历26个字母
        if(i != aim){  
            st[i]++;    //新来的字母单独做为一个子串，所以需要加1
        }
    }
}
int main(){
    long long sum = 0;  //用于记录子串数值总和sum
    long long x = 0;  //用于记录新生成的子串数值和
    cin>>chs;
    int n = strlen(chs);
    for(int i = 0;i<n;i++){
        x = x + st[chs[i]-'a'] + 1;  //文章中的x1=x0+增量
        sum = sum + x;   //文章中的sum1=sum0+1+x.
        update(chs[i]); 
    }
    cout<<sum;
    return 0;
}