Omar And Strings
Practice
4.6 (13 votes)
Approved
Hash maps
Medium
Ready
String manipulation
Z algorithm
Z Algorithm
Problem
76% Success 1025 Attempts 30 Points 1s Time Limit 256MB Memory 1024 KB Max Code

Today while studying Omar reads many words in books and references. He feels bored enough to stop reading he has noticed something strange. All the words in some statement can be read the same from left to right and from right to left. Later, Omar discovered that this type of strings is called palindromic strings.

After some thinking Omar wants to create a new type of strings and gives that type a name derived from his name, so he invents a new type of strings and calls it omeric strings. Omar's friend Hazem loves prefixes and Eid loves suffixes so Omar will take this into consideration while inventing the new type. To make a string omeric from a string s you should concatenate the longest palindromic suffix with the longest palindromic prefix.

Then Omar wants to know how many times each prefix of his omeric string can be found in this string as a substring. Substring of the string can be defined by two indices L and R and equals \(s_L s_{L+1} \dots s_R\).

Input:

The first line of the input contains a string s of length N, \(1 \le N \le 10 ^ 5\).
The given string consists only of lowercase characters.

Output:

Print the omeric string in the first line. Print the frequency of each prefix in the second line.

Please login to use the editor

You need to be logged in to access the code editor

Loading...

Please wait while we load the editor

Loading...
Results
Custom Input
Run your code to see the output
Submissions
Please login to view your submissions
Similar Problems
Points:30
17 votes
Tags:
AlgorithmsApprovedKMP AlgorithmMediumZ algorithmZ-algorithm
Points:30
5 votes
Tags:
AlgorithmsDynamic ProgrammingMediumReadyZ algorithmZ-algorithm
Points:30
7 votes
Tags:
AlgorithmsKMP AlgorithmMediumOpenString ManipulationZ algorithmZ-algorithm