CUC-SUMMER-4-E

E - Pretty Poem

ZOJ - 3818

---

Poetry is a form of literature that uses aesthetic and rhythmic qualities of language. There are many famous poets in the contemporary era. It is said that a few ACM-ICPC contestants can even write poetic code. Some poems has a strict rhyme scheme like "ABABA" or "ABABCAB". For example, "niconiconi" is composed of a rhyme scheme "ABABA" with A = "ni" and B = "co".

More technically, we call a poem pretty if it can be decomposed into one of the following rhyme scheme: "ABABA" or "ABABCAB". The symbol A, B and C are different continuous non-empty substrings of the poem. By the way, punctuation characters should be ignored when considering the rhyme scheme.

You are given a line of poem, please determine whether it is pretty or not.

Input
There are multiple test cases. The first line of input contains an integer T indicating the number of test cases. For each test case:

There is a line of poem S (1 <= length(S) <= 50). S will only contains alphabet characters or punctuation characters.

Output
For each test case, output "Yes" if the poem is pretty, or "No" if not.

Sample Input
3
niconiconi~
pettan,pettan,tsurupettan
wafuwafu
Sample Output
Yes
Yes
No

---

题意：如果一首诗符合ABABA或ABABCAB那么是一首好诗，判断一首诗是否为好诗，不考虑标点符号

解法：枚举法，枚举A和B的长度，不用枚举C的长度，C的长度可以通过AB求出，然后切割字符串，得到A、B、C，如果输入字符串S=A+B+A+B+A，或S=A+B+A+B+C+A+B，则满足好诗的条件。注意A、B、C不相同且长度大于0。

代码：

#include<iostream>
#include<string>
#include<cstring>
using namespace std;
char a[60];
string b;
bool com1()
{
    int n=b.length();
    for(int i=1;i<=n/3;i++){
        for(int j=1;j<=n/2;j++){
            if(i*3+j*2==n){
                string A,B;
                A=b.substr(0,i);
                B=b.substr(i,j);
                if(A+B+A+B+A==b&&A!=B)
                    return true;
            }
        }
    }
    return false;
}
bool com2()
{
    int n=b.length();
    for(int i=1;i<=n/3;i++){
        for(int j=1;j<=n/3;j++){
            if(i*3+j*3<n){
                string A,B,C;
                A=b.substr(0,i);
                B=b.substr(i,j);
                C=b.substr(i+j+i+j,n-i-j-i-j-i-j);
                if(A+B+A+B+C+A+B==b&&A!=B&&A!=C&&B!=C)
                    return true;
            }
        }
    }
    return false;
}
int main()
{
    int num;
    cin>>num;
    while(num--){
        cin>>a;
        b="";
        int n=strlen(a);
        for(int i=0;i<n;i++)
            if(isalpha(a[i]))
                b+=a[i];
        com1()||com2()?cout<<"Yes"<<endl:cout<<"No"<<endl;      
    }
}