Longest Prefix and Suffix
Given a string of character, find the length of longest proper prefix which is also a proper suffix.
First line is T number of test cases. Each test case has one line denoting the string of length less than 100000.
Print length of longest proper prefix which is also a proper suffix.
Input: T = 1 "abcdabc" Output: 3 //as prefix "abc" is the longest proper prefix //present in the string. Input: T = 1 "abcdefghijklm" Output: 0 //as there is no prefix which is a suffix. Input: T = 1 "aaaaaaa" Output: 6 //as for proper prefix we can't have entire length // as the prefix so only length possible is 6.
1) Brute Force Approach
Since the longest proper prefix which is also a suffix cannot be equal to the entire length of the string because it can't overlap each other, so we break the string from mid-point and start matching left and right string. If they are equal return size of any one string else try for shorter lengths on both sides.
2) Better approach: Using longest prefix-suffix array of KMP algorithm
Here we will use an array which represents the length of the longest proper prefix which is also equal to the suffix of the array.
Here we use lps array which stores the length of a longest proper prefix which is the equal suffix, each index of lps represent the current index lps upto that index comparison, initialize lps=0, since it is not possible to have proper prefix-suffix with one letter then we declare two variable j and i by which we compare the characters.
Output:need an explanation for this answer? contact us directly to get an explanation for this answer