Prefix Fix

Time Limit: 1 sec

 

The Problem

Prefix is the substring of the main string which always starts from the first character. A string has length-1 prefix substrings.

Example: abca has 3 prefix substrings that are “a”, “ab”, “abc”.

 

Suffix is the substring of the main string which always starts from the last character. A string has length-1 suffix substrings.

Example: abca has 3 suffix substrings that are “a”, “ca”, “bca”.

 

Your task is to find longest prefix substring of S, which is also a suffix substring of S. For example “a” is the longest prefix substring of “abca”, which is a suffix too.

 

The Input

Input contains several lines. Each line will contain a string S in lowercase letter. The length of the string not more than 10000. Input is terminated by EOF.

 

The Output

For each lines of input print a single line of output which is the longest prefix of given string which is a suffix too. If there is no such prefix substring, just print “Fix”.

 

Sample Input

aabaaba

abcabc

abcd

 

Sample Output

aaba

abc

Fix

 

 

 

Inter University Programming Contest - 2017 [BGC Trust University Bangladesh]

Problem Setter: Milton Deb