题目链接：http://codeforces.com/problemset/problem/385/B
题目意思：给定一条只有小写英文组成的序列，需要找出至少包含一个“bear”的单词的子序列个数。注意，子序列的下标编号是连续的，也就是sisi?+?1... sj?，不是这种sisk... sj?。（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.
1 #include <iostream> 2 #include <cstdio> 3 #include <cstdlib> 4 #include <string> 5 using namespace std; 6 7 string s, t; 8 9 int main() 10 { 11 int i, j, cnt, len, t1, t2; 12 cin >> s; 13 j = cnt = 0; 14 len = s.size(); 15 for (i = 0; i < len; i++) 16 { 17 t = s.substr(i, 4); // 从序列中找4个连续的字母 18 if (t == "bear") 19 { 20 cnt++; // 统计单个的bear数，不是组合数（组合数中不包括单个的bear！） 21 if (i == 0) // 前面没有字母 22 t1 = len-1-(i+3); // 后面有多少个字母 23 else 24 { 25 t2 = len-1-(i+3); 26 t1 = (i-j) * t2 + i-j + t2; // 组合数由3个部分组成 27 } 28 cnt += t1; 29 j = i+1; // 保存上一个“bear”的“e”的下标 30 i += 3; // 一个“bear”占4个字符 31 } 32 } 33 printf("%d\n", cnt); 34 return 0; 35 }