子串分值

关键词

排列组合, 连续子串

分析

题目样例大小是$1 \leq n \leq 100000$. 对于$O(n^2)$算法而言, 不可能通过所有的评测用例.但初步观察, 是很容易得到$O(n^2)$算法

$O(n^2)$枚举出所有的子串, 然后可基于上一个子串的唯一字符数, 可$O(1)$内完成子串中唯一字符数的统计.

此时, 如果要追求$O(n)$算法, 步骤中是不可能包含列出子串这一过程, 应该是寻找一种方法, 直接根据字符当前的位置, 直接得出该字符对答案的贡献.

分析可得

等

思路

先考虑这样一个问题, 假设一个字符串XXAXX. 问包含子串A有多少种?

首先子串一定是连续的, 而对于连续的, 只要==确定其开头和结尾就可唯一确定一个子串. 开头可选择 XXA中任意一个字符, 而结尾也可以从AXX中任意选择一个字符. 所以, 包含A的子串有$3 * 3 = 9$种. (排列和组合)

回到题目中, 为了保证子串中唯一出现一个字符, 我们必须在==开头字符和结尾字符==中做出适当的修改. 例如ABABC中的, 第二个A. 只含有一个A的子串, 开头只能在 BA(自身)做出选择, 而对于结尾在 A(自身)BC中做出选择. 所以答案是 2 * 3 = 6.

到此, 我们已经有一种办法, 可以在$O(1)$计算出. 一个位置上的字符对答案的贡献.

贡献为:

下标从0开始

( 当前X的位置 - 上一个X的位置) * (下一个X的位置 - 当前X的位置)

上一个X的位置: 默认为-1 (可以带入具体事例, 尝试一下)

下一个X的位置: 默认为 字符串长度

算法

1. 统计每一个字符出现的位置 $O(n)$
2. 算法每一个位置字符对答案的贡献 $O(n)$

总时间复杂度$O(n)$

#include <iostream>
#include <string>
#include <vector>
using namespace std;
typedef long long int ll;
void solve(){
    vector<vector<ll>> posChar(26);
    string input;
    cin >> input;
    // 初始化, 每一个都先扔-1
    for(auto &item: posChar)
        item.push_back(-1);
    // 扔位置
    for(int i = 0; i < input.size() ; ++i){
        posChar[input[i] - 'a'].push_back(i);
    }
    // 扔末尾位置
    for(auto &item: posChar)
        item.push_back(input.size());

    ll ans = 0;
    // 统计答案
    for(auto &item: posChar){
        for(int i = 1; i < (ll)item.size() - 1; ++i){
            ans += (item[i] - item[i-1]) * (item[i + 1] - item[i]);
        }
    }

    cout << ans;

}

int main(){
    solve();
    return 0;
}