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

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:

APPAPT

Sample Output:

2

题意

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

思路

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

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

状态计算：

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

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

代码

#include<bits/stdc++.h>
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;
}