一、题目

1、题目描述

2、输入输出

2.1输入

2.2输出

3、原题链接

Problem - 1168B - Codeforces

---

二、解题报告

1、思路分析

一眼没思路，打个暴力试试

因为如果 s[l, r] 是一个好字符串，那么s[i, r]一定也是好字符串，其中i < l

那么我们枚举左端点l，找到最近的r，那么l的贡献就是n - r

看起来是O(n^2)的，跑了下过了，而且只跑了46ms，这明明是O(n)复杂度才能跑出来的时间

然后看样例：

这个样例其实是在暗示只要长度大于等于9那么都是好字符串，这个可以二进制枚举2 ^ 9种字符串验证一下发现都是，那么对于长度大于9的字符串，由于它含长度为9的子串，所以它也是好字符串

所以我们的暴力做法其实是O(n)的

2、复杂度

时间复杂度： O(9n)空间复杂度：O(n)

3、代码详解

​

#include <bits/stdc++.h>
using i64 = long long;

int main () {
    std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);
    std::string s;
    std::cin >> s;
    i64 res = 0;
    int n = s.size();
    std::vector<int> r(n + 1, n);
    for (int i = n - 1; ~i; i -- ) {
        r[i] = r[i + 1];
        for (int j = 1; i + j * 2 < r[i]; j ++ )
            if (s[i] == s[i + j] && s[i] == s[i + 2 * j])
                r[i] = i + 2 * j;
        res += n - r[i];
    }
    std::cout << res;
    return 0;
}