首页 > 其他 > 详细

JZOJ 3843. 寻找羔羊(agnus)

时间:2019-11-06 16:18:49      阅读:85      评论:0      收藏:0      [点我收藏+]

题目

Description

给定一个由小写字母组成的字符串,寻找包含“agnus”(羔羊)的子串的个数。注意:当且仅当两个子串的起始位置和终点不同时,这两个子串属于不同的子串。
 

Input

只有一个字符串,表示题中所述的字符串。

Output

仅一个数字,表示满足题意的子串个数。
 

Sample Input

agnusbgnus

Sample Output

6
【样例解释】
    6个子串分别是:agnus、agnusb、agnusbg、agnusbgn、agnusbgnu、agnusbgnus。
 

Data Constraint

对于 40%的数据,字符串长度<=1000
对于 100%的数据,字符串长度<=30000

分析

 

  • 首先,显然算一个前面*后面
  • 但是我们需要去重
  • 直接记录上一个的位置
  • 少算就OK

 

代码

 

 

 1 #include <cmath>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <iostream>
 5 #include <algorithm>
 6 #define ll long long
 7 using namespace std;
 8 int main()
 9 {
10     int ans=0,last=-1;
11     string s;
12     cin>>s;
13     for (int i=0;i<=s.size()-4;i++)
14     {
15         if(s[i]==a&&s[i+1]==g&&s[i+2]==n&&s[i+3]==u&&s[i+4]==s)
16         {
17             if (last!=-1) ans+=(i-last)*(s.size()-i-4);
18             else ans+=(i+1)*(s.size()-i-4);
19             last=i;
20         } 
21     } 
22     cout<<ans;
23     return 0;
24 }

 

 

 

JZOJ 3843. 寻找羔羊(agnus)

原文:https://www.cnblogs.com/zjzjzj/p/11805758.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!