博客

字符串 APPAPT 中包含了两个单词 PAT，其中第一个 PAT 是第 2 位§，第 4 位(A)，第 6 位(T)；第二个 PAT 是第 3 位§，第 4 位(A)，第 6 位(T)。

现给定字符串，问一共可以形成多少个 PAT？

输入格式：

输入只有一行，包含一个字符串，长度不超过10^5 ，只包含 P、A、T 三种字母。

输出格式：

在一行中输出给定字符串中包含多少个 PAT。由于结果可能比较大，只输出对 1000000007 取余数的结果。

输入样例：

APPAPT

输出样例：

2

代码：

//之前题意理解错误，以为只需要找到最后的T和A，然后确定在最后的A的之前的P的数量就行了。当然不对咯。

//后来好久才意识到，A和T的位置和数量会使 符合要求的结果多出很多。

//A在PAT的中间位置，可以在遍历字符串时，碰到A，就计算该位置之前P的数量乘以之后T的数量，累加起来就行了。

//其中测试点2是非常长的字符串 
#include<cstdio>
#include<cstring>
const int maxn=100005;
const long long max2=1000000007;
int main()
{
	char a[maxn];
	if(scanf("%s",a));
	int i;
	int p[maxn]={0};
	int t[maxn]={0};
	int len=strlen(a);
	for(i=1;i<len;i++){
		if(a[i-1]=='P') p[i]=p[i-1]+1;//代表当前位置之前有多少P 
		else p[i]=p[i-1]; 
		if(a[len-i]=='T') t[len-i-1]=t[len-i]+1;//代表当前位置之后有多少T 
		else t[len-i-1]=t[len-i];		
	}
	long long sum=0;
	for(i=1;i<len-1;i++){
		if(a[i]=='A'){
			sum=(sum+p[i]*t[i])%max2;
		}
	}	
	printf("%lld\n",sum);	
	return 0;
}