LPS - Longest Palindromic Substring
A palindrome is a string that is the same as its reverse. Example "malayalam", "dad", "appa" etc. In this problem you are asked to find the length of the longest contiguous substring of a given string, which is a palindrome.
Input
The first line consists of a single integer N, the number of characters in the string. 1 <= N <= 100000.
Second line is a string with N characters, where the characters are always lowercase English letters, i.e. 'a' to 'z'.
Output
A single line with an integer representing the length of longest palindromic substring.
Example
Input:
5
ababa
Output:
5
Input: 5 ababa Output: 5
hide comments
|
fahimcp495:
2020-01-01 20:43:03
AC using manacher's algo |
|
maruf_1604089:
2019-12-23 06:29:10
AC in 1 go using Palindrome Tree |
|
mac1309:
2019-07-27 08:10:57
suffix array implementation ending up in segmentation fault. <snip>
|
|
beingbmc:
2019-07-01 21:49:47
Used manacher's.
|
|
sifat_15:
2018-09-19 09:22:09
Hlw, @akash1518
|
|
akash1518:
2018-08-28 17:12:12
binary search +hashing (nlogn)
|
|
neha__mishra:
2018-08-02 09:46:17
I tried many versions for this problem including dynamic programming but each of them gave wrong answer after test case 16 or 14 or 15 ........ I wonder if the test cases can be downloaded from somewhere or how to know about the critical test cases? |
|
Shubhashsi Roy Dipta:
2018-04-12 13:58:47
Test case is weak
|
|
ammen99:
2018-01-01 09:27:17
authors, please update the constraints in the problem statement, N can be as big as 5*10^5 |
|
Krishna Mohan:
2017-11-18 11:52:11
It seems like upper limit of n is not 10^5, but more than that |
| Added by: | Srivatsan B |
| Date: | 2009-06-04 |
| Time limit: | 1s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | All except: ERL JS-RHINO NODEJS PERL6 VB.NET |
| Resource: | http://opc.iarcs.org.in/problems/iarcs-feb05-ad-1 |
RSS