admin管理员组

文章数量:1646246

字符串APPAPT中包含了两个单词“PAT”,其中第一个PAT是第2位(P),第4位(A),第6位(T);第二个PAT是第3位(P),第4位(A),第6位(T)。

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

输入格式:

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

输出格式:

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

输入样例:
APPAPT
输出样例:
2

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#define MOD 1000000007
int main()
{
    char str[100010];//10的5次方是6位数,不是5位数,不要犯这种低级错误
    gets(str);
//    char str[100010]="APPAPT";
    int strLength=strlen(str);
    int leftNumberP[100010]={0};
    int rightNumberT[100100]={0};
    for(int i=0;i<strLength;++i){
        if(str[i]=='P'){
            leftNumberP[i+1]=leftNumberP[i]+1;//这里为什么左值要用i+1呢,考虑到i=0时候,没有-1,所以错开一位
        }
        else{
            leftNumberP[i+1]=leftNumberP[i];
        }
    }
    for(int j=strLength-1;j>=0;--j){//这里非常容易出错,顺手就写成++j;一定要小心
        if(str[j]=='T'){
            rightNumberT[j]=rightNumberT[j+1]+1;
        }
        else{
            rightNumberT[j]=rightNumberT[j+1];
        }
    }
    int sum=0;//记录PAT的个数
    for(int k=0;k<strLength;++k){
        if(str[k]=='A'){
            sum=(sum+leftNumberP[k+1]*rightNumberT[k])%MOD;//注意这里leftNumberP向右错开了一位,这里一定要记得除MOD
        }
    }
    printf("%d\n",sum);//题目要求防止sum过大,sum设置成除以1000000007的余数,第二次修改,不能这里除,应该在开头计算的除才有效果
    return 0;
}

本文标签: 有几个PAT