【PAT甲级 - C++题解】1093 Count PAT‘s

✍个人博客：https://blog.csdn.net/Newin2020?spm=1011.2415.3001.5343
📚专栏地址：PAT题解集合
📝原题地址：题目详情 - 1093 Count PAT’s (pintia.cn)
🔑中文翻译：PAT 计数
📣专栏定位：为想考甲级PAT的小伙伴整理常考算法题解，祝大家都能取得满分！
❤️如果有收获的话，欢迎点赞👍收藏📁，您的支持就是我创作的最大动力💪

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 10⁵ 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:

APPAPT
1

Sample Output:

2
1

题意

给定一个字符串，请你求出字符串中包含的 PAT 的数量。

思路

这道题可以用动态规划状态机来做，将需要匹配的字符串 PAT 转换成状态，为了方便计算，我们将空格设置为初始状态 0 ，然后在从前往后遍历字符串 s 的时候就计算一遍所有的状态，每个状态都是由它前一个状态转移过来。

状态表示： $f[i][j]$ 表示只考虑前 i 个字母且走到了状态 j 的所有路线的数量。

状态计算：

如果当前遍历的字符不属于 PAT 中的字符，则将上一轮对应状态的数量转移到这一轮中：$f[i][j]=f[i-1][j]$

如果满足要求，则加上上一轮该状态的前一个状态的数量：$f[i][j]=(f[i][j]+f[i-1][j-1])\%MOD$

代码

#include
using namespace std;

const int N = 100010, MOD = 1000000007;
char s[N], p[] = " PAT";
int f[N][4];

int main()
{
    cin >> s + 1;
    int n = strlen(s + 1);

    f[0][0] = 1;  //初始化
    for (int i = 1; i <= n; i++)   //遍历每个字符
        for (int j = 0; j < 4; j++)    //遍历每个状态
        {
            f[i][j] = f[i - 1][j];  //将上一轮的状态转移过来
            //如果满足条件，则更新数量
            if (s[i] == p[j])  f[i][j] = (f[i][j] + f[i - 1][j - 1]) % MOD;
        }

    cout << f[n][3] << endl;

    return 0;
}
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