题意描述

给定一个仅有小写字母组成的字符串，寻找包含$\text{agnus}$（羔羊）的子串的个数。

注意：当且仅当两个子串的起始位置和终点不同时，这两个子串属于不同的子串。

输入格式

输入只有一行，包含一个字符串，表示题中所述的字符串。

输出格式

输出只有一行，仅一个数字，表示满足题意的子串个数。

Input & Output ‘s examples

Input ‘s eg

agnusbgnus

Output ‘s eg

样例解释

6个子串分别是：$\text{agnus}$、$\text{agnusb}$、$\text{agnusbg}$、$\text{agnusbgn}$、$\text{agnusbgnu}$、$\text{agnusbgnus}$。

数据范围与约定

对于 $40\%$的数据，保证$|s| \leq 10^3$
对于 $100\%$的数据，保证$|s| \leq 3 \times 10^4$

分析

一道递推好题。

从样例解释里可以看出，每出现$\text{agnus}$之后，其后边的每个字符均能够形成一个子串。

同理，每个$\text{agnus}$之前的每个字符也能够形成一个子串。

这样的话，答案为每个$\text{agnus}$前后字符的数量之积。

然而，若有两个$\text{agnus}$相连，则会出现重复计算。因此需要注意去重。

设$li$表示第$i$个 $\text{agnus}$ 左边的字符，则去重的方式为$l_i = l_i - l{i - 1}$。因为$li$与$l{i - 1}$的公共部分已经在计算$l_{i - 1}$时计算过。

剩下的见代码注释。

Code[Accepted]

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<stack>
#include<queue>
#include<deque>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<cstdlib>
#include<cctype>
#include<cmath>

#define ll long long 
#define I inline
#define N 30010

using namespace std;

string s;
ll l[N] , r[N] , cnt;

int main(){
    cin >> s;
    if(s.length() < 5){ //特判，当字符串长度小于5时根本不会出现agnus。
        puts("0");
        return 0;
    }
    s = '0' + s;    //将字符串与0拼接，即若原字符串为agnus,则拼接后为0agnus，以便于之后的操作
    for(int i = 0; i < s.length(); i ++){
        if(s[i] == 'a' && s[i + 1] == 'g' && s[i + 2] == 'n' && s[i + 3] == 'u' && s[i + 4] == 's'){
            ++ cnt; //若找到agnus，则记录
            l[cnt] = i; //记录其左边的字符数
            r[cnt] = s.length() - (i + 4);  //记录右边的字符数
        }
    }
    ll ans = 0;
    for(int i = 1; i <= cnt; i ++){
        ans += (l[i] - l[i - 1]) * r[i];    //去重并统计答案
    }
    cout << ans << "\n";
    return 0;
}