题解：CF385B Bear and Strings

这道题需要求字符串的子串中包含 bear 的个数。

最简单的算法是枚举子串的起始位置与结束位置，如果包含 bear，就将答案的数量 $+1$。但是分析复杂度可知，两层循环加上字符串的截取与查找，是无法通过总长度 $s = 5000$ 的，因此我们就要考虑每一个 bear 字串对答案的贡献。

for (int i = 0;i < str.size ();++i)
{
    for (int j = i + 1;j < str.size ();++j)
        {
        string _n = str.substr (i,j - i + 1);
        if (_n.find("bear") != -1) ans++;
    }
}

遍历整个序列，如果查找到 bear，就会对后面的子串产生影响。从第 $i$ 位查找到最后，如果包含 bear，那么只要另外子串包含这个 bear，那么就会是答案增加。但同时要记得去除重复计算的部分，因此就有：枚举到第 $i$ 位，若包含 bear(从第 $i$ 位到最后)，则答案会增加整个字符串的长度 $- i - 3 - $ bear 第一次出现的位置。这样就减少了一层循环，可以通过此题。

#include <iostream>
#include <string>
#include <cstdio>
using namespace std;
int main ()
{
    string str;int ans = 0;
    cin>>str;
    for (register int i = 0;i < str.size ();++i)
    {
        string d1 = str.substr (i,str.size () - i);
        if (d1.find("bear") != -1) ans += str.size() - i - 3 - d1.find("bear");
    }
    printf ("%d\n",ans);
    return 0;
}