学步园

题目链接：uva 11888 - Abnormal 89's

题目大意：给定一个字符串，判断该字符串是否由两个非空的回文串组成，在判断是否是一个回文。

解题思路：KMP，将字符串翻转，然后用翻转后的字符串去匹配原字符串，然后匹配到最后的匹配值为p，那么后p个字符组成的字符串一定是回文串，并且所有的失配p都是回文，然后在用原串去匹配翻转后的字符串，同样的道理，如果两边有相加等于n（字符串长度）的，那么就一定可以拆分成两个回文串。

#include <cstdio>
#include <cstring>
#include <set>
#include <algorithm>

using namespace std;
const int maxn = 200005;

int n, jump[maxn];
char s[maxn], t[maxn];

void init () {
    scanf("%s", s+1);
    n = strlen(s+1);

    for (int i = n; i; i--)
        t[i] = s[n-i+1];
    t[n+1] = '\0';
//    printf("%s\n%s\n", s+1, t+1);
}

void get_jump (char* str) {

    int p = 0;
    for (int i = 2; i <= n; i++) {
        while (p && str[p+1] != str[i])
            p = jump[p];

        if (str[p+1] == str[i])
            p++;
        jump[i] = p;
    }
}

int find (char* x, char* y) {
    int p = 0;
    for (int i = 1; i <= n; i++) {
        while (p && x[p+1] != y[i])
            p = jump[p];

        if (x[p+1] == y[i])
            p++;
    }
    return p;
}

int judge () {
    int ret = 0;
    set<int> vec;

    get_jump(s);
    int k = find(s, t);

    if (k == n)
        ret = 1;

    while (k) {
        vec.insert(k);
        k = jump[k];
    }

    get_jump(t);
    k = find(t, s);

    while (k) {
        if (k != n) {
            if (vec.find(n - k) != vec.end())
                return 2;
        }
        k = jump[k];
    }

    return ret;
}

int main () {
    int cas;
    scanf("%d", &cas);
    while (cas--) {
        init();
        int k = judge();

        if (k)
            printf("%s\n", k == 2 ? "alindrome" : "palindrome");
        else
            printf("simple\n");
    }
    return 0;
}