class Main{
public static void main
(String[] args
){ Main m = new Main();
m.test("7888885466662716666".getBytes());
m.test("788888546666271888".getBytes());
m.test("12233344441111222334".getBytes());
}
private void test(byte[] input){
String result
= findLongestRepeatedSubsequence
(input
); System.
out.
println("The longest repeating subsequence in " + new String(input
) + " is: " + result
); System.
out.
println("----------"); }
private String findLongestRepeatedSubsequence
(byte[] byteMass
){ // Convert the bytes to a String:
// Loop as long as this String has at least 1 character:
while(bytesAsString.length() > 0){
// Split the String into characters, where each character is a loose String of length 1
String[] charsAsStringArray
= bytesAsString.
split(""); int length = charsAsStringArray.length;
int maxCount = 0;
int startingIndex = 0;
// Loop `i` in the range [0, length_of_String_array)
for(int i = 0; i < length; i++){
// Take the substring where the first `i` characters are removed
String subString
= bytesAsString.
substring(i
); String currentChar
= charsAsStringArray
[i
]; // Count the amount of subsequent times the current character occurs at the start of the substring
int count = subString.length() - subString.replaceFirst(currentChar+"*", "").length();
// If this count is larger than our current maxCount:
if(count > maxCount){
// Replace the maxCount with this count
maxCount = count;
// And set the index where we've found this longest subsequence (`i`) as well
startingIndex = i;
}
}
// After we've checked all substrings, get the longest subsequence we've found
String longestSub
= bytesAsString.
substring(startingIndex, startingIndex
+ maxCount
); // Split the entire String with this longest subsequence
int occurrenceCounter = bytesAsString.split(longestSub, -1).length - 1;
System.
out.
println("Current longest subsequence: " + longestSub
+ ", which occurs " + occurrenceCounter
+ " time(s)"); // If we've found a subsequence that occurs at least twice:
if(occurrenceCounter > 1){
// Return it as result
return longestSub;
}
// If this longest subsequence only occurs once:
else{
System.
out.
println("Before removing: " + bytesAsString
); // Remove the first character of this found subsequence from the String
bytesAsString = bytesAsString.substring(0, startingIndex) +
(startingIndex < length-1 ?
bytesAsString.substring(startingIndex + 1)
:
"");
System.
out.
println("After removing: " + bytesAsString
); }
}
// Mandatory return if the input is empty
return null;
}
}