算法學習之路|我要通過（20）

“答案正确”是自動判題系統給出的最令人歡喜的回複。本題屬于PAT的“答案正确”大派送 —— 隻要讀入的字元串滿足下列條件，系統就輸出“答案正确”，否則輸出“答案錯誤”。

得到“答案正确”的條件是：

字元串中必須僅有P, A, T這三種字元，不可以包含其它字元；

任意形如 xPATx 的字元串都可以獲得“答案正确”，其中 x 或者是空字元串，或者是僅由字母 A 組成的字元串；

如果 aPbTc 是正确的，那麼 aPbATca 也是正确的，其中 a, b, c 均或者是空字元串，或者是僅由字母 A 組成的字元串。

現在就請你為PAT寫一個自動裁判程式，判定哪些字元串是可以獲得“答案正确”的。

輸入格式： 每個測試輸入包含1個測試用例。第1行給出一個自然數n (<10)，是需要檢測的字元串個數。接下來每個字元串占一行，字元串長度不超過100，且不包含空格。

輸出格式：每個字元串的檢測結果占一行，如果該字元串可以獲得“答案正确”，則輸出YES，否則輸出NO。

輸入樣例：

8

PAT

PAAT

AAPATAA

AAPAATAAAA

xPATx

PT

Whatever

APAAATAA

輸出樣例：

YES

NO

思路：

一開始半個多小時都無從下手，最後看了題解才明白是一個數學歸納法的簡單模拟題，而我想到kmp變形去了。。。

其實讀題的時候，看到第三個條件，. 如果 aPbTc 是正确的，那麼 aPbATca 也是正确的。。中間增加一個A而右邊卻增加了一個a，增長呈現線性關系，P和T之間的A的總數增了一個，而T右邊卻增加了a，我們得以得出數學關系式

a中A的個數*（b中A的個數+1） = c中A的個數+a中A的個數

至此就可以編碼了

哦，還有一點細節

*PT中間必須要有A