题目描述

字符串APPAPT中包含了两个单词“PAT”，其中第一个PAT是第2位(P),第4位(A),第6位(T)；第二个PAT是第3位(P),第4位(A),第6位(T)。
现给定字符串，问一共可以形成多少个PAT？

输入描述

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

输出描述

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

输入例子

APPAPT

输出例子

2

我的代码

//不是满分
#include<stdio.h>
#include<string.h>
int main(){
    char a[100000];
    int len,i,j,k,t=0,n;
    scanf("%s",&a);
    len=strlen(a);
    for(i=0;i<len;i++){
        for(j=i+1;j<len;j++){
            for(k=j+1;k<len;k++){
                if(a[i]=='P'&&a[j]=='A'&&a[k]=='T'){
                    t++;
                }
            }
        }
    }
    n=t%1000000007;
    printf("%d",n);
    return 0;
} 

我的分析

这道题的第一反应就是暴力解决，直接用一个三重循环来按照P,A,T的顺序来找，编译的时候当然不是满分，运行超时了3个测试点，但是也得了15分，在真正考试的时候可以先把自己先想到的简单方法提交上去，尽量多的得分，如果有时间在后面可以想的全面一点。

正确代码

#include<stdio.h>
#include<string.h>
int main(){
    char a[100000];
    int len1,i=0,j=0,k=0;
    scanf("%s",a);
    len1=strlen(a);
    
    while(len1>0){
        len1--;
        if(a[len1]=='T'){
            i++;
        }
        if(a[len1]=='A'){
            j=(i+j)%1000000007;
        }
        if(a[len1]=='P'){
            k=(k+j)%1000000007;
        }
    }
    printf("%d",k);
    return 0;
} 

思路

这个算法是从后往前开始查找，先找到‘T’，然后让i加1，接着是再找到‘A’，然后让记录‘AT’的j来加上i，最后是再找到‘P’，让记录‘PAT’，的k加上j，最后输出k就可以了。