【2020.9.12SSL模拟賽T1】字元串【字元串】

題目描述

小熊有一個由小寫英文字母組成的字元串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對( i , j ) (為：( 1 ， 6 ) ， ( 1 ， 7 ) ， ( 1 ， 8 ) ， ( 2 ， 6 ) ， ( 2 ， 7 ) ， ( 2 ， 8 ) ， ( 3 ， 6 ) ， ( 3 ， 7 ) ， ( 3 ， 8 )

分析

先存好有bear的區間。枚舉每個區間，看看有沒有包含bear的區間，有的話答案加1.

上代碼

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;

string a;
int x[3001],y[3001],k,ans;

int main() 
{
	cin>>a;
    for(int i=0;i<=a.length()-3;i++)
    {
    	if(a[i]=='b'&&a[i+1]=='e'&&a[i+2]=='a'&&a[i+3]=='r')
    	{
    		k++;
    		x[k]=i;
    		y[k]=i+3; 
		}
	}
	for(int i=0;i<=a.length()-1;i++)
    {
    	for(int j=0;j<=a.length()-1;j++)
    	{
    		for(int f=1;f<=k;f++)
    		{
    			if(i<=x[f]&&j>=y[f])
    			{
    				ans++;
    				break;
				}
			}
		}
	}
	cout<<ans;
	return 0;
}