题目描述
字符串 APPAPT
中共包含两个 PAT
作为子串。
第一个子串由第二,第四和第六个字符组成,第二个子串由第三,第四和第六个字符组成。
现在给定一个字符串,请你求出字符串中包含的 PAT
的数量。
输入格式
共一行,包含一个由大写字母 $P$,$A$,$T$ 构成的字符串。
输出格式
输出字符串中包含的 PAT
的数量。
由于结果可能很大,请你输出对 $10^9+7$ 取模后的结果。
数据范围
给定字符串的长度不超过 $10^5$。
输入样例:
APPAPT
输出样例:
2
算法1 (60分代码)
(暴力枚举) $O(n^2)$
C++ 代码
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
typedef long long LL;
int main(){
string s;
cin>>s;
LL cnt1=0,res=0;
for(int i=0;i<s.size();i++){
if(s[i]=='P') cnt1++;
if(s[i]=='A'){
LL cnt2=0;
for(int j=i+1;j<s.size();j++){
if(s[j]=='T') cnt2++;
}
res+=cnt1*cnt2;
}
}
cout<<res<<endl;
return 0;
}
算法2
(巧算) $O(n)$
思路:
预处理出每个字符左边有多少个字符P,再预处理出每个字符右边有多少个字
符T,最后再循环判断当前字符是否是A,如果是,就用乘法原理算出当前可以增
加多少个PAT
C++ 代码
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
typedef long long LL;
const int N=1e5+10,mod=1e9+7;
LL cnt1[N],cnt2[N];
int main(){
string s;
cin>>s;
LL res=0;
for(int i=1;i<s.size();i++){
if(s[i-1]=='P') cnt1[i]=cnt1[i-1]+1;
else cnt1[i]=cnt1[i-1];
}
for(int i=s.size()-1;i>=0;i--){
if(s[i+1]=='T') cnt2[i]+=cnt2[i+1]+1;
else cnt2[i]=cnt2[i+1];
}
for(int i=0;i<s.size();i++){
if(s[i]=='A') res+=cnt1[i]*cnt2[i]%mod;
}
cout<<res%mod<<endl;
return 0;
}