【题解】字符串

矫情吗；* 2021-11-11 03:58 265阅读 0赞

# 题目描述 #

小熊有一个由小写英文字母组成的字符串s=s1s2...sn。小熊想要计算s中有多少子串包含字符串“bear”，也就是找出满足字符串x（i，j）=si......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。

请帮助小熊解决这个问题。

# 输入格式 #

一行，包含一个非空字符串s。数据保证字符串s中只包含小写英文字母。

# 输出格式 #

一行，包含一个整数，表示这个问题的答案。

## ##

# **输入样例** #

bebearar

# **输出样例** #

## ##

# **样例说明** #

符合条件的9对（i，j）分别是：（1，6），（1，7），（1，8），（1，6），（2，7），（2，8），（3，6），（3，7），（3，8）。

# **数据规模** #

对于50%的数据：1≤n≤200。

对于100%的数据：1≤n≤3000。

# 题解 #

容易想到，我们设$size$为字符串长度，那么字符串的$\[i,size)$（$i$从$0$开始）中包含"bear"的以第$i$位开头的序列数量为$size - lt - 3$，其中$lt$为离$i$最近的"bear"的位置。我们从后往前枚举$i$，顺便更新$lt$即可。（其实这也算是尺取法吧）

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <iostream>
    #include <string>
    
    using namespace std;
    
    string str;
    int ans;
    
    int main()
    {
        cin >> str;
        int lt = str.size() - 3;
        for(register int i = str.size() - 4; i >= 0; --i)
        {
            if(str[i] == 'b' && str[i + 1] == 'e' && str[i + 2] == 'a' && str[i + 3] == 'r') lt = i;
            ans += str.size() - lt - 3;
        }
        cout << ans;
        return 0;
    }

参考程序

转载于:https://www.cnblogs.com/kcn999/p/10803994.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211109/40d55917a1834960b871ceb7196c8388.png