PAT-Basic-1040. 有几个PAT

字符串APPAPT中包含了两个单词“PAT”,其中第一个PAT是第2位(P),第4位(A),第6位(T);第二个PAT是第3位(P),第4位(A),第6位(T)。

现给定字符串,问一共可以形成多少个PAT?

输入格式:

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

输出格式:

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

输入样例:

输出样例:


注意优化……三重循环能解,但是一定会超时!

思路大体是这样的:

  1. 读入字符串,通过声明的结构体数组count实现对字符串的重新储存和计数,重新处理即为对相邻重复字符串的合并与计数。
  2. 从count末端开始,把T的计数向前依次叠加至距离其前最近的A的next上,获得每个A后有多少个T。
  3. 仍然从count末端开始,把每个A所对应的num*next,即此处后AT总个数向前叠加至A的num上(这里我当时应该是写烦了,感觉最好是P的next上,尽管效果都一样),这样每个A的位置就储存了其(包括它自身)后方共有多少个AT。
  4. 从count前端开始,累加(每个P的num*其后第一个A的num)计算PAT的数量。

代码如下:

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注