In this post we'll see a Java program to find the length of the longest proper prefix of a given string that is also a suffix of
the same string. Proper prefix means a prefix that is not equal to the whole string. For example, proper prefixes of String
"abc" are "a", "ab", along with the empty string "" but it doesn't include "abc".
Coming to our requirement of finding the length of the longest proper prefix of a given string that is also a suffix of the same
string, here are some examples.
Input is String s = "ababab";
Then output is- 4 as "abab" is the LPS here.
Input is String s = "aaaaa";
Then output is- 4 as "aaaa" is the LPS here.
Input is String s = "abcde";
Then output is- 0 as there is no prefix which is a suffix too.
Input is String s = "aabcdaabc"
Then output is- 4 as "aabc" is the LPS here.
Here 2 ways are given to write Java program for this problem-
- Using brute force approach
- Using LPS array part of the KMP pattern matching algorithm
1. Length of the longest proper prefix of a given string that is also a suffix - Java program with brute force approach
In this approach you will have to match each possible prefix (0 to n-1 for string of length n) with the same length suffix.
If all characters are same then it’s a match and that length becomes the current LPS.
For the program, two pointers r and l are used with r always starting from 0 and l starts from l – i (for 1 <= i < n).
if characters at r and l matches then you keep incrementing both r and l. If l becomes equal to n (length of string) that becomes
the current LPS.
You can visualize it as this-
This will be the case when i = 3, at that time r = 0 and l = 7 - 3 = 4. Here len = 7
Here is the Java program
public class LongestPrefixSuffix {
public static void main(String[] args) {
//String str = "aabcdaabc";
String str = "abcdabc";
System.out.println(getLPSLengthTwoP(str));
}
static int getLPSLengthTwoP(String str) {
int len = str.length();
int length = 0;
// You don't want suffix to reach till 0th char,
// thats why i starts from 1
for(int i = 1; i < len; i++) {
int r = 0;
int l = len - i;
while(r < i && l < len ){
// if no match then come out of the inner loop
if(str.charAt(r) != str.charAt(l)) {
break;
}
r++;
l++;
}
// If l goes till the end of the String
if(l == len)
length = r;
}
return length;
}
}
Output
3
The time complexity of this approach is O(n2) as the outer loop traverse the whole string length, whereas inner loop
may run i times.
Space complexity of this approach is constant i.e. O(1) as fixed number of integer variables are used.
2. Using LPS array part of the KMP algorithm - Java Program
With in the KMP pattern matching algorithm there is a part to create a longest prefix suffix (LPS) array. What is done in this
logic is to traverse the length of the String n (0 to (n-1)) and for each index i you look for the longest prefix that is
also a suffix for the substring 0 to i.
For example, if string is "ababcab" then the created LPS array would be- [0, 0, 1, 2, 0, 1, 2]
When i is 2 then there is a LPS of length 1 with in the substring "aba".
When i is 3 then there is a LPS of length 2 with in the substring "abab".
When i is 5 then there is a LPS of length 1 with in the substring "ababca".
When i is 6 then there is a LPS of length 2 with in the substring "ababcab".
The last entry in the created LPS array gives the length of the longest proper prefix which is also a suffix with in the given
string.
Here is the Java program
public class LongestPrefixSuffix {
public static void main(String[] args) {
String str = "ababccababa";
//String str = "aaaa";
System.out.println(computeLPSArray(str));
}
static int computeLPSArray(String str) {
int n = str.length();
int length = 0; // Length of the previous longest prefix suffix
int[] lps = new int[n];
int i = 1;
lps[0] = 0; // lps[0] is always 0
while (i < n) {
if (str.charAt(i) == str.charAt(length)) {
lps[i] = ++length;
i++;
} else {
if (length != 0) {
// Use LPS array to find a smaller prefix
length = lps[length - 1];
} else {
// if No common prefix/suffix found
lps[i] = 0;
i++;
}
}
}
return lps[n-1];
}
}
Output
3
With in the program this is the part which causes confusion-
if (length != 0) {
// Use LPS array to find a smaller prefix
length = lps[length - 1];
}
Let's try to visualize it to get proper understanding.
When i = 10, for the string of length 11 as shown above, the LPS array at that stage would look like-
[0, 0, 1, 2, 0, 0, 1, 2, 3, 4, 0]
Which means length variable at this time has value 4 and comparison fails for-
str.charAt(i) == str.charAt(length)
which takes the control to else part, that's where there is an optimization to look for the previous longest prefix/suffix by
assigning length this way- length = lps[length - 1]; and start matching from there. It works because based on the new value of length, it is guaranteed that the highlighted parts will be same and we can start comparison after that position. Thus the final LPS array with all the elements will look like this-
[0, 0, 1, 2, 0, 0, 1, 2, 3, 4, 3]
Making the longest proper prefix that is also the suffix as 3.
With LPS array, time complexity becomes linear O(n) as there is only one traversal of String and each character may get
processed at most two times-
- Once when i increments.
- Once when length backtracks due to mismatch
Needs auxiliary space for the LPS array, so the space complexity is O(n).
That's all for the topic Longest Prefix Suffix Java Program. If something is missing or you have something to share
about the topic please write a comment.
You may also like
