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

这里可以复制样例：

样例输入：

agnusbgnus

样例输出：

这里是链接：【入门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代码：

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 #include<algorithm>
 5 #define MAXN 30010
 6 using namespace std;
 7 char str[MAXN];
 8 char goal[10]="agnus"; 
 9 int l[MAXN],r[MAXN]; //记录区间 
10 int len,ans;
11 int cont;
12 
13 int main(){
14     cin>>str+1;
15     len=strlen(str+1);
16     for(int i=1;i<=len;i++){
17         int cnt=0;bool flag=0;
18         while(str[i]==goal[cnt]){
19             i++;cnt++;flag=1;
20             if(cnt==5){
21                 cont++;
22                 i--;flag=0;
23                 l[cont]=i-4;
24                 r[cont]=i;
25                 break;
26             }
27         }
28         if(flag==1) i--;//因为while循环里面i多加了一次，所以减回来。 
29     }
30     for(int i=1;i<=cont;i++){
31         ans+=(l[i]-l[i-1])*(len-r[i]+1);
32     }
33     printf("%d
",ans);
34     return 0;
35 }

【入门OJ】2003

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