Join Regular Classroom : Visit ClassroomTech

Longest Prefix Which is the Suffix – Infytq 2019 Solve

/ Miscellaneous / By

Problem: Given a string s, find the length of the longest prefix which is also the suffix. The prefix and suffix should not overlap.

Input Format: First line contains a single integer, the number of testcases n. Next n line contains n strings as input.

(NOTE: The actual problem didn’t have the number of testcases as input. But for your better convenience we have worked with testcases.)

Sample Input:

2
abcdabc
ababa

Sample Output: 

3
1

Explanation: Here in the first example, the longest prefix in the string is “abc” which is also present in the end as suffix, the length of this suffix is 3. Hence it returned 3.

Here you may think the longest prefix is “aba” but it overlaps the letter ‘a’ with the suffix “aba” hence it won’t be the case. The longest prefix without an overlap with the suffix is ‘a’. Its length is 1 hence, it returned 1.

Solution: We strongly recommend you to try the problem first before moving to the solution.

# Solution of Longest Prefix Which is the Suffix problem in Python 
# www.codewindow.in 

def solve(str):
    length=len(str)
    half=length//2    # Integer Division
    
    for i in range (half, 0, -1):
        prefix=str[0 : i]
        suffix=str[length-i : length]
    
        if prefix==suffix:
            print(len(prefix))
            break

# Driver Code
test_case=int(input());     # Take number of testcases
while(test_case):
    str=input()
    solve(str)
    test_case-=1

Input:

2
abcdabc
ababa

Output:

3
1

Follow Us

You Missed