字符串

題目大意：

有一個字符串，問有子串“bear”的子串有多少個

原題：

題目描述

小熊有一個由小寫英文字母組成的字符串s = s1s2…sn。小熊想要計算s中有多少子串包含字符串“bear”，也就是找出滿足字符串x(i, j)= sisi+1…sj 包含至少一個字符串“bear”的 (i, j)對數（1≤i≤j≤n）。
字符串x(i, j)包含字符串“bear”定義為存在一個整數k（i≤k≤j-3），滿足sk=b，sk+1=e，sk+2=a，sk+3=r。
請幫助小熊解決這個問題。

輸入

輸入共1行，包含一個非空字符串s。數據保證字符串s中只包含小寫英文字母。

輸出

輸出共1行，包含一個整數，表示這個問題的答案。

輸入樣例

bebearar

輸出樣例

9

說明

【輸入輸出樣例說明】

符合條件的9對(i, j)為：(1，6)，(1，7)，(1，8)，(2，6)，(2，7)，(2，8)，(3，6)，(3，7)，(3，8)。

【數據說明】

對于50%的數據，1≤n≤200。
對于100%的數據，1≤n≤3000。

解題思路

找到一個“bear”然后看前后各可以延伸多少，然后相乘，為了去重，必須將上一個“bear”拆開，也就是從上一個“bear”的“e”開始就可以把他們拆開了，最后加在一起就可以了

代碼：

#include<cstdio> #include<iostream> #include<cstring> #include<string> using namespace std; int h,ans,l; string str; int main() {getline(cin,str);l=str.size();str=' '+str;//方便計算h=1;//預處理for (int i=1;i<=l-3;++i)if (str[i]=='b'&&str[i+1]=='e'&&str[i+2]=='a'&&str[i+3]=='r')//“bear”{ans+=(i-h+1)*(l-i-3+1);//前面的和后面的h=i+1;//去重}printf("%d",ans);//輸出 }

總結

以上是生活随笔為你收集整理的【字符串】字符串的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。