longestRepeatingSubstring function

String longestRepeatingSubstring(String s)

Finds the longest substring in a string that appears at least twice using binary search and rolling hash.

This function uses a combination of binary search and Rabin-Karp rolling hash to efficiently find the longest repeating substring in the input string s.

Time Complexity: O(n log n), where n is the length of the string. Space Complexity: O(n)

Example:

String s = "banana";
print(longestRepeatingSubstring(s)); // Outputs: "ana"

Implementation

String longestRepeatingSubstring(String s) {
  int n = s.length;
  int left = 1, right = n, resLen = 0, resStart = 0;
  while (left <= right) {
    int len = (left + right) ~/ 2;
    final idx = _search(s, len);
    if (idx != -1) {
      resLen = len;
      resStart = idx;
      left = len + 1;
    } else {
      right = len - 1;
    }
  }
  return s.substring(resStart, resStart + resLen);
}