Last Updated: 25 Nov, 2021

# Longest Prefix Which is Suffix

Moderate

## Problem statement

#### If there's no such string return an empty string "".

##### Example:
Input: ‘str’ = ‘ababcdabab’

Output: 'abab'

Explanation:
Here the prefix ‘abab’ is equal to the suffix ‘abab’. The length of the prefix is 4. There's no other prefix that has length > 4 and is also present as a suffix. Hence the answer is 'abab'.
##### Input Format:
The first line of input contains a string ‘str’ representing the input string.

##### Output Format:
Return a single integer representing the length of the largest prefix which is also a suffix. If there's no such string return an empty string.

##### Note :
You do not need to print anything. It has already been taken care of. Just implement the given function. '-1' will be printed for returned strings that are empty.

## Approaches

### 01 Approach

In this approach, we will check all the possible prefixes of the given string. Since we have to find the longest non-overlapping prefix, we will start from the prefix of ‘N/2’ length, where ‘N’ is the length of the string, and then we keep decreasing the prefix, length as long as it doesn’t match with the suffix of the same length.

Algorithm:

• In the isEqual(str1, str2) function:
• Takes two string and returns a True if all characters match in two strings, ‘str1’ and ‘str2
• In the given function:
• Set N as the length of ‘str’
• Iterate preLen through N-1 to 0
• Set prefix as substring of str from 0 to preLen - 1
• Set suffix as substring of str from n - preLen to n - 1
• If suffix is equal to prefix then return prefix
• If the function reaches out of the loop return “”