MSUBSTR - Mirror Strings !!!

no tags 

 

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.Consider string "lalit" then its mirror string will be "tilal".
Input :
There are t numbers of test cases (t<=100) 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.
Sample test cases :
Input :
3
lalit
abedcdetr
abcde
Output :
3 1
5 1
1 5
Time Limit : 1 sec

     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 (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.

 

Sample test cases :

Input :

3

lalit

abedcdetr

abcde

 

Output :

3 1

5 1

1 5

 

 

 

 


hide comments
suvro_coder: 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. ;)

Gaurav Dahima: 2016-08-31 20:01:27

@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
Ayush Mishra: 2015-06-17 22:01:18

Did it without manchester algorithm. Used polynomial hashing and binary search. Complexity per testcase is O(n log n).

FoolForCS: 2015-05-19 21:32:25

Simple and so elegant. Wow-ed by this algorithm!

Last edit: 2015-05-19 21:33:42
vip_yadav: 2015-01-11 13:26:50

very nice problem !!! finally AC>>>!!!!

The Arrow: 2014-08-19 19:27:30

@admin please delete spoiler comment
@nitesh kumar please dont spoil the problem

nitesh kumar: 2014-07-17 14:20:26

manacher algorithm
nice explantion:http://leetcode.com/2011/11/longest-palindromic-substring-part-ii.html

utpal kumar jha: 2013-12-25 16:24:27

finallyy :D :D

satya hemanth: 2013-11-06 10:15:50

century!!

tuhin: 2013-06-12 18:05:58

@problemsetter please avoid spoilers .
@Pradeep mathesh please dont make it obvious

Last edit: 2013-07-12 04:56:52

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