MSUBSTR  Mirror Strings !!!
As we all know Utkarsh is very good at solving number based problems, this time Arpit thinks smartly and gives Utkarsh to solve a problem on Strings. Arpit gives Utkarsh a string and challenges him to find the length of largest substring that have its mirror string same as its original one and number of such substrings. Now Utkarsh is buzy at preparing Avishkar papers so he asks you to help him in doing this task.
Eg. for mirror string : Consider string "lalit" then its mirror string will be "tilal".
Input :
There are t numbers of test cases (t<=200) followed t lines where each line contains a character string of lower case characters (az) of length l (1>=l<=3000).
Output :
There will be two integers per line separated by space indicating the length of largest substring which have its mirror string same and number of such substrings.
Sample test cases :
Input :
3
lalit
abedcdetr
abcde
Output :
3 1
5 1
1 5
hide comments
suvro_coder:
20170618 23:50:47
AC in 2 goes. Used maacher's algorithm.


Gaurav Dahima:
20160831 20:01:27
@Rahul Dubey O(n*n) is giving TLE


Ayush Mishra:
20150617 22:01:18
Did it without manchester algorithm. Used polynomial hashing and binary search. Complexity per testcase is O(n log n). 

FoolForCS:
20150519 21:32:25
Simple and so elegant. Wowed by this algorithm! Last edit: 20150519 21:33:42 

vip_yadav:
20150111 13:26:50
very nice problem !!! finally AC>>>!!!! 

The Arrow:
20140819 19:27:30
@admin please delete spoiler comment


nitesh kumar:
20140717 14:20:26
manacher algorithm


utpal kumar jha:
20131225 16:24:27
finallyy :D :D 

satya hemanth:
20131106 10:15:50
century!! 

tuhin:
20130612 18:05:58
@problemsetter please avoid spoilers .

Added by:  ! include(L.ppt) 
Date:  20120921 
Time limit:  0.639s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  MNNIT OPC 21092012 