fork download
  1. class Main{
  2. public static void main(String[] args){
  3. Main m = new Main();
  4. m.test("7888885466662716666".getBytes());
  5. m.test("788888546666271888".getBytes());
  6. m.test("12233344441111222334".getBytes());
  7. }
  8.  
  9. private void test(byte[] input){
  10. String result = findLongestRepeatedSubsequence(input);
  11. System.out.println("The longest repeating subsequence in " + new String(input) + " is: " + result);
  12. System.out.println();
  13. System.out.println("----------");
  14. }
  15.  
  16. private String findLongestRepeatedSubsequence(byte[] byteMass){
  17. // Convert the bytes to a String:
  18. String bytesAsString = new String(byteMass);
  19. // Loop as long as this String has at least 1 character:
  20. while(bytesAsString.length() > 0){
  21. // Split the String into characters, where each character is a loose String of length 1
  22. String[] charsAsStringArray = bytesAsString.split("");
  23. int length = charsAsStringArray.length;
  24. int maxCount = 0;
  25. int startingIndex = 0;
  26. // Loop `i` in the range [0, length_of_String_array)
  27. for(int i = 0; i < length; i++){
  28. // Take the substring where the first `i` characters are removed
  29. String subString = bytesAsString.substring(i);
  30. String currentChar = charsAsStringArray[i];
  31. // Count the amount of subsequent times the current character occurs at the start of the substring
  32. int count = subString.length() - subString.replaceFirst(currentChar+"*", "").length();
  33. // If this count is larger than our current maxCount:
  34. if(count > maxCount){
  35. // Replace the maxCount with this count
  36. maxCount = count;
  37. // And set the index where we've found this longest subsequence (`i`) as well
  38. startingIndex = i;
  39. }
  40. }
  41. // After we've checked all substrings, get the longest subsequence we've found
  42. String longestSub = bytesAsString.substring(startingIndex, startingIndex + maxCount);
  43. // Split the entire String with this longest subsequence
  44. int occurrenceCounter = bytesAsString.split(longestSub, -1).length - 1;
  45. System.out.println("Current longest subsequence: " + longestSub + ", which occurs " + occurrenceCounter + " time(s)");
  46. // If we've found a subsequence that occurs at least twice:
  47. if(occurrenceCounter > 1){
  48. System.out.println();
  49. // Return it as result
  50. return longestSub;
  51. }
  52. // If this longest subsequence only occurs once:
  53. else{
  54. System.out.println("Before removing: " + bytesAsString);
  55. // Remove the first character of this found subsequence from the String
  56. bytesAsString = bytesAsString.substring(0, startingIndex) +
  57. (startingIndex < length-1 ?
  58. bytesAsString.substring(startingIndex + 1)
  59. :
  60. "");
  61. System.out.println("After removing: " + bytesAsString);
  62. System.out.println();
  63. }
  64. }
  65. // Mandatory return if the input is empty
  66. return null;
  67. }
  68. }
Success #stdin #stdout 0.11s 2184192KB
stdin
Standard input is empty
stdout
Current longest subsequence: 88888, which occurs 1 time(s)
Before removing: 7888885466662716666
After removing:  788885466662716666

Current longest subsequence: 8888, which occurs 1 time(s)
Before removing: 788885466662716666
After removing:  78885466662716666

Current longest subsequence: 6666, which occurs 2 time(s)

The longest repeating subsequence in 7888885466662716666 is: 6666

----------
Current longest subsequence: 88888, which occurs 1 time(s)
Before removing: 788888546666271888
After removing:  78888546666271888

Current longest subsequence: 8888, which occurs 1 time(s)
Before removing: 78888546666271888
After removing:  7888546666271888

Current longest subsequence: 6666, which occurs 1 time(s)
Before removing: 7888546666271888
After removing:  788854666271888

Current longest subsequence: 888, which occurs 2 time(s)

The longest repeating subsequence in 788888546666271888 is: 888

----------
Current longest subsequence: 4444, which occurs 1 time(s)
Before removing: 12233344441111222334
After removing:  1223334441111222334

Current longest subsequence: 1111, which occurs 1 time(s)
Before removing: 1223334441111222334
After removing:  122333444111222334

Current longest subsequence: 333, which occurs 1 time(s)
Before removing: 122333444111222334
After removing:  12233444111222334

Current longest subsequence: 444, which occurs 1 time(s)
Before removing: 12233444111222334
After removing:  1223344111222334

Current longest subsequence: 111, which occurs 1 time(s)
Before removing: 1223344111222334
After removing:  122334411222334

Current longest subsequence: 222, which occurs 1 time(s)
Before removing: 122334411222334
After removing:  12233441122334

Current longest subsequence: 22, which occurs 2 time(s)

The longest repeating subsequence in 12233344441111222334 is: 22

----------