abc串(字符串水题)
程序员文章站
2022-05-29 16:05:03
...
给出一串由’a’, ‘b’,'c’组成的字符串,求该串最多包含多少个abc子串。结果对 1000000007 取模。
输入格式:
第一行一个数字 n ,表示字符串的长度
第二行一个字符串,表示这个字符串。
输出格式:
输出一行,一个数表示该字符串最多包含多少个abc子串
输入样例:
5
abbbc
3
aab
4
abcc
输出样例:
在这里给出相应的输出。例如:
3
0
2
提示:
第一组样例:abc子串为1,2,5 1,3,5 1,4,5 总共为3
第二组样例:没有abc子串 总共为0
第三组样例:abcc:子串为 1,2,3 1,2,4 总共为2
数据范围:
对于30%数据 3≤n≤200
对于50%数据3≤n≤2000
对于100%数据3≤n≤2∗10
5
错误思路:分别记录 a,b,c的下标,三层for找出abc
虽然可行,但是复杂度太高,运行超时
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int main(){
int n;
cin >> n;
string s;
cin >> s;
ll a = 0, b = 0, c = 0;
for(int i = 0; i < s.length(); i++){
if(s[i] == 'a') a++;
else if(s[i] == 'b') b += a;
else if(s[i] == 'c') c += b, c %= 1000000007;
}
cout << c%1000000007 << endl;
}
总结对于找指定子串的类型题 ,可以作表来判断子串元素的变化情况,来判断最终的逻辑结构
上一篇: CZML Packet相关声明详细内容
下一篇: C语言 将字符串中数字字符全部删除