EPALIN - Extend to Palindrome
Your task is, given an integer N, to make a palindrome (word that reads the same when you reverse it) of length at least N (1 <= N <= 100,000). Any palindrome will do.
Easy, isn't it? That's what you thought before you passed it on to your inexperienced team-mate. When the contest is almost over, you find out that that problem still isn't solved. The problem with the code is that the strings generated are often not palindromic. There's not enough time to start again from scratch or to debug his messy code.
Seeing that the situation is desperate, you decide to simply write some additional code that takes the output and adds just enough extra characters to it to make it a palindrome and hope for the best. Your solution should take as its input a string and produce the smallest palindrome that can be formed by adding zero or more characters at its end. The input string will consist of only upper and lower case letters.
Example
Input: aaaa abba amanaplanacanal xyz Output: aaaa abba amanaplanacanalpanama xyzyxNote: 1. All palindromes are considered case-sensitive (i.e. 'Aa' is not a palindrome). 2. Large I/O. Be careful in certain languages.
hide comments
slothsphereoj:
2024-02-22 03:30:00
Excellent problem on kmp or z-algo indeed. |
|
cjn2007:
2021-09-27 14:28:38
Got Accepted int the second chance because of a small mistake.....
|
|
maheshwari7778:
2021-04-17 08:29:41
lodu h accepted in in one go>>>>>>
|
|
s_tank00_:
2020-12-29 08:13:09
accepted in 1 go ..... |
|
samartha_5611:
2020-08-19 12:00:53
It can be very easily solved with Z-algo.....
|
|
hackerbhaiya:
2020-06-18 23:29:33
@ babur yes it can be solved using Z algo ….. i + z[i] should be equal to some value (Hint) |
|
amansahu112:
2020-04-20 11:43:36
simple code but great concept of KMP |
|
prudhvi_495:
2019-06-04 16:21:17
EXCELLENT APPLICATION OF KMP Algo |
|
elmer_fudd:
2018-10-28 08:35:25
anyone give me z - algorithm solution please |
|
nmouad21:
2018-01-23 21:59:22
Cool problem Last edit: 2018-01-23 21:59:45 |
Added by: | Muntasir Azam Khan |
Date: | 2009-03-22 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ERL JS-RHINO |
Resource: | Own problem, used in Next Generation Contest 5 |