cf B Bear and Strings

题意：给你一个字符串，然后找多少区间内含有“bear”，输出数目；

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 char str[5001];
 7 int pos[50001];
 8 
 9 int main()
10 {
11     while(scanf("%s",str)!=EOF)
12     {
13         int k=strlen(str);
14         memset(pos,0,sizeof(pos));
15         int cnt=0;
16         for(int i=0; i+4<=k; i++)
17         {
18             if(str[i]=='b'&&str[i+1]=='e'&&str[i+2]=='a'&&str[i+3]=='r')
19             {
20                 pos[cnt++]=i+3;
21             }
22         }
23         int ans=0;
24         int last=0;
25         for(int i=0; i<cnt; i++)
26         {
27             if(pos[i]-3==0)
28             {
29             ans+=(k-pos[i]);
30 
31             last=pos[i]-3;
32             }
33             else
34             {
35                 if(i==0)
36                 {
37                     ans+=(pos[i]-3+1)*(k-pos[i]);
38                 }
39                 else
40                 ans+=(pos[i]-3-last)*(k-pos[i]);
41                 last=pos[i]-3;
42             }
43         }
44         printf("%d
",ans);
45     }
46     return 0;
47 }

View Code