【入门OJ】2003: [Noip模拟题]寻找羔羊

这里可以复制样例：

样例输入：

agnusbgnus

样例输出：

6

这里是链接：【入门OJ】2003: [Noip模拟题]寻找羔羊

这里是题解：

题目是求子串个数，且要求简单去重。

对于一个例子（agnus这个单词只出现过一次）：abcagnusbgnus

它的满足子串就有以下几种情况：

①自身：agnus；

②和前面的字符组合：abcagnus、bcagnus、cagnus;

③和后面的字符组合：agnusbgnus、agnusbgnu、agnusbgn、agnusbg、agnusb;

④两边都组合：abcagnusbgnus、abcagnusbgnu、abcagnusbgn、abcagnusbg、abcagnusb、bcagnusbgnus、bcagnusbgnu、

bcagnusbgn、bcagnusbg、bcagnusb、cagnusbgnus、cagnusbgnu、cagnusbgn、cagnusbg、cagnusb；

所以首先对于只出现过一次的来说：ans+=(前面字符个数+后面字符个数+前面字符个数*后面字符个数+1)；

简化一下就是：ans+=(前面字符个数+1)*（后面字符个数+1）；

然而这只是对于只出现过一次的情况。因为要有去重操作，所以并不能直接用于多次出现情况。

首先看重复出现的情况：如果将样例*2：agnusbgnusagnusbgnus

按照以上操作的话：算第一个羔羊会出现：agnusbgnusagnusb（和后面的字符组合）

算第二个羔羊的时候也会出现同样子串：（两边都组合）

所以能看出，对于每个羔羊，利用只出现一次的情况来解决是有区间限制的。而这个区间就是向前不能延伸到

之前出现的羔羊，向后无限延伸。（反之，也成立）

具体的区间就是：

①前区间：上一个agnus的a位置到当前agnus的a位置前一个的位置。

②后区间：当前agnus的s位置后一个的位置到最后一个位置。

（因为求ans是前后都要加1的，所以前区间直接是agnus的a位置，后区间直接是agnus的s位置）

这里是AC代码：

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<algorithm>

 #define MAXN 30010

 using namespace std;

 char str[MAXN];

 char goal[]="agnus";

 int l[MAXN],r[MAXN]; //记录区间

 int len,ans;

 int cont;

 int main(){

     cin>>str+;

     len=strlen(str+);

     for(int i=;i<=len;i++){

         int cnt=;bool flag=;

         while(str[i]==goal[cnt]){

             i++;cnt++;flag=;

             if(cnt==){

                 cont++;

                 i--;flag=;

                 l[cont]=i-;

                 r[cont]=i;

                 break;

             }

         }

         if(flag==) i--;//因为while循环里面i多加了一次，所以减回来。

     }

     for(int i=;i<=cont;i++){

         ans+=(l[i]-l[i-])*(len-r[i]+);

     }

     printf("%d\n",ans);

     return ;

 }

【入门OJ】2003

梦想总是要有的，万一实现了呢？