PAT_1093

1093 Count PAT’s

题目描述

The string APPAPT contains two PAT‘s as substrings. The first one is formed by the 2nd, the 4th, and the 6th characters, and the second one is formed by the 3rd, the 4th, and the 6th characters.

Now given any string, you are supposed to tell the number of PAT‘s contained in the string.

Input Specification:

Each input file contains one test case. For each case, there is only one line giving a string of no more than 105 characters containing only P, A, or T.

Output Specification:

For each test case, print in one line the number of PAT‘s contained in the string. Since the result may be a huge number, you only have to output the result moded by 1000000007.

Sample Input:

1
APPAPT

Sample Output:

1
2

思路

求出一个字符串中所包含的连续或不连续的子串”PAT”的个数, 首先想到的是遍历字符串中的P,然后确定A,最后寻找T,确定前面两个,子串个数为A位置后面T字符的个数,但是这样的思路,时间复杂度为O(n^2),时间应该会超限

既然确定P时间复杂度很高,我们可以确定中间的A,做一次预处理,求出A位置之前的P出现的次数,A位置之后T出现的次数,这样将两个出现的次数相乘,即可确定当前中间A固定的子串PAT的个数

程序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <set>
#include <queue>
#include <map>
#define INF 0x3f3f3f3f

using namespace std;

const int maxn = 1e5+10;
const int mod = 1000000007;
typedef long long ll;
string s;
int p[maxn],t[maxn];
int main()
{
cin >> s;
int len = s.length();
if(s[0] == 'P') p[0] = 1;
if(s[0] == 'T') t[0] = 1;

for(int i = 1;i < len;i ++)
{
if(s[i] == 'P')
p[i] = p[i-1] + 1,t[i] = t[i-1];
else if(s[i] == 'T')
t[i] = t[i-1] + 1,p[i] = p[i-1];
else
t[i] = t[i-1],p[i] = p[i-1];
}

int num_t = t[len-1];
int ans = 0;
for(int i = 0;i < len;i ++)
{
if(s[i] == 'A')
{
ans += (p[i] * (num_t - t[i])) % mod;
ans %= mod;
}
}
printf("%d\n",ans);
return 0;
}
-------------本文结束感谢您的阅读-------------
显示 Gitment 评论