对于一个字符串s,我们定义s的分值f(s),为s中恰好出现一次的字符个数,现在给定一个字符串,请你计算对于所有s的非空子串的和是多少,用c++
时间: 2024-12-22 18:27:24 浏览: 9
在C++中,我们可以使用哈希集合(unordered_set)来存储每个字符及其出现次数。遍历整个字符串,对于每个字符,我们检查它是否只出现了一次,如果满足条件,就将其添加到集合中,并更新相应的分值。然后,对于每个子串,我们再次检查每个字符的出现次数,累计那些出现恰好一次的字符的数量作为当前子串的分值。
以下是解决这个问题的一种可能的C++代码实现:
```cpp
#include <string>
#include <unordered_map>
int calcSubstringsSum(std::string s) {
int sum = 0;
std::unordered_map<char, int> count;
for (size_t i = 0; i < s.length(); ++i) {
if (count.find(s[i]) != count.end()) {
count[s[i]]++;
} else {
count[s[i]] = 1;
}
// 计算当前字符的分值,即出现1次的字符个数
int freq = count[s[i]];
if (freq == 1) {
sum += 1;
}
// 更新子串前缀的计数
if (i > 0) {
sum -= count[s[i - 1]]; // 如果上一个字符减少,当前字符可能恢复为1次
}
}
return sum * (s.length() + 1); // 外加整个字符串本身
}
// 示例:
std::string str = "abacaba";
int result = calcSubstringsSum(str);
```
这个函数`calcSubstringsSum`会返回字符串s中所有非空子串分值之和。注意这里假设了字符串中没有重复的连续字符。如果你需要考虑这种情况,可以稍作调整。
阅读全文