[SPOJ] O(n^2) test case for PALDR's simple algorithm

Thanks to misof, there's a counterexample to show that the simple algorithm for PALDR is still O(n^2):

(abcd)^n xy (dcba)^n

Problem is rejudged. Some previously AC solutions got TLEs.

[SPOJ] EPALIN

Consider the longest border (LB) problem:

Input: string s[1..n] of length n
Output: LB(s) = max{ i | i < n AND s[1..i] = s[n-i+1..n] }

LB(s) can be computed in O(n) (this problem was introduced in the KMP algorithm)

EPALIN is essentially to find the longest palindrome suffix:
LS(s) = min{i | s[i..n] is a palindrome}

We reduce LS to LB. Consider the string:
$s^\prime = s_ns_{n-1}...s_1 \alpha\beta s_1s_2...s_n$ in which $\alpha \neq \beta$

It is easy to prove that LS(s') = LB(s)

Note: palindromic property can sometimes be handled by consider the string $SS^R$