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 busy at preparing Avishkar papers so he asks you to help him in doing this task.

E.g. 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 (a-z) 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.

Example

Input:
3
lalit
abedcdetr
abcde

Output:
3 1
5 1
1 5

Added by:! include(L.ppt)
Date:2012-09-21
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:MNNIT OPC 21-09-2012

hide comments
2024-06-12 18:07:07
I have a test string "tilit".
someone can tell me the output for this test?
[Simes]: 5 1

Last edit: 2024-06-13 14:01:21
2021-10-28 13:06:06
AC in one go with O(n).
2019-09-21 12:48:53
QL^2logL passes, weak test cases.
2017-06-18 23:50:47
AC in 2 goes. Used maacher's algorithm.
Test cases here:
http://spojtoolkit.com/history/MSUBSTR
Thank me later. ;)
2016-08-31 20:01:27 Gaurav Dahima
@Rahul Dubey O(n*n) is giving TLE
bottom up giving TLE, any other method apart from Manacher’s Algorithm ???

Last edit: 2016-09-23 08:26:25
2015-06-17 22:01:18 Ayush Mishra
Did it without manchester algorithm. Used polynomial hashing and binary search. Complexity per testcase is O(n log n).
2015-05-19 21:32:25 FoolForCS
Simple and so elegant. Wow-ed by this algorithm!

Last edit: 2015-05-19 21:33:42
2015-01-11 13:26:50 vip_yadav
very nice problem !!! finally AC>>>!!!!
2014-08-19 19:27:30 The Arrow
@admin please delete spoiler comment
@nitesh kumar please dont spoil the problem
2014-07-17 14:20:26 nitesh kumar
manacher algorithm
nice explantion:http://leetcode.com/2011/11/longest-palindromic-substring-part-ii.html
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.