【题解】abc_牛客博客

思路：

题目的意思是求字符串s中有多少个子串（不一定要连续）为’abc’
一开始想到先找到a的位置，再找到a后面b的位置，然后ans加上b的后面有多少个c，可是这样的话每查找一次a的时间是n，查找a后面b的位置的时间是n，总的时间复杂度就是n方，会超时，有没有什么更好的方法呢？
不如稍微改变一下思路，先找到b的位置，再看看b的前面有多少个a，b的后面有多少个c，二者相乘就是包含这个b的子串’abc’的数量，用ans累加起来就行了
至于b的前面有多少个a，后面有多少个c，可以预处理

code:

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
long long anss;
int a[N],c[N],n;
/*a[i]:i位置前面有多少个a c[i]:i位置后面有多少个c */
char s[N],C;
//s[]:字符串 
int main()
{
    while ((C=getchar())!='\n') s[n++]=C;n--;
    for (int i=0,j=n;i<n,j>=0;i++,j--) //预处理 
    {
    	a[i]=a[i-1]+(s[i]=='a');
    	c[j]=c[j+1]+(s[j]=='c');	
	}
	for (int i=0;i<n;i++)
	  if (s[i]=='b') anss+=a[i]*c[i];//累加答案 
	printf("%lld\n",anss);
	return 0;
}

其实这个代码还可以优化，预处理出每个b的位置，这样就不用for循环一遍找’b’了