codeforces B. Bear and Strings 解题报告

题目链接：http://codeforces.com/problemset/problem/385/B

题目意思：给定一条只有小写英文组成的序列，需要找出至少包含一个“bear”的单词的子序列个数。注意，子序列的下标编号是连续的，也就是s_is_i + 1... s_j ，不是这种s_isk... s_j 。（k!=i+1）

     我的做法是每找到一个“bear”就计算出它的组合数，累加所有找到的“bear ”组合数即为答案。假设序列长度为len，先用string中的substr()来找出单词“bear”中“b”的下标（i），然后计算出这个单词之前（i个，因为下标是从0开始的）和之后有多少个字母（len-1-(i+3)）。组合数由3个部分组成：（1）i个字母+“bear”  （2）“bear"+ len-1-(i+3) 个字母  （3）i个字母+“bear” + len-1-(i+3) 个字母。注意，计算这3个部分的组合数，不是简单的 i*t2 + i + t2，因为会有重复！！！拿“wwbearwbearo”这个例子来说，第一个遇到的“bear”组合数是21，没有错误（其中所有组合数中包括"wwbearwbear",  "wwbearwbearo"， "wbearwbear"， "wbearwbearo"，"bearwbear"，"bearwbearo" 这6个），然而到了第二个遇到的“bear” ，如果还是这样算的话，这6个组合数会被重复计算，实质上第2个“bear”前的字母不再是7个（wwbearw），而是4个（earw），即从第一个“bear”中的第2个"e"到第2个“bear”的字母数。所以我们需要引入多一个j，保存当前第i个“bear“前的第i-1个“bear”的“e”这个下标。注意，初始j 的值为0.

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <string>
using namespace std;

string s, t;

int main()
{
    int i, j, cnt, len, t1, t2;
    cin >> s;
    j = cnt = 0;
    len = s.size();
    for (i = 0; i < len; i++)
    {
        t = s.substr(i, 4);  // 从序列中找4个连续的字母
        if (t == "bear")
        {
            cnt++;   // 统计单个的bear数，不是组合数（组合数中不包括单个的bear！）
            if (i == 0)     // 前面没有字母
                t1 = len-1-(i+3);  // 后面有多少个字母
            else
            {
                t2 = len-1-(i+3);        
                t1 = (i-j) * t2 + i-j + t2;  // 组合数由3个部分组成
            }
            cnt += t1;
            j = i+1;    // 保存上一个“bear”的“e”的下标
            i += 3;    // 一个“bear”占4个字符
        }
    }
    printf("%d
", cnt);
    return 0;
}