I need to find the length of the longest repeating pattern in a sequence of beads represented as a string. The string can be up to 1 million characters long. What is the most efficient algorithm for solving this problem, ideally running in linear time O(n) or close to it?

considered a few approaches for this problem:

Naive Approach: I initially tried a brute-force method where I checked all possible substrings and counted their occurrences. This approach quickly proved inefficient for large strings due to its high time complexity.

Suffix Array and LCP Array: I explored using suffix arrays combined with Longest Common Prefix (LCP) arrays. This method is known to be effective for substring problems but might be complex to implement and manage for very large strings.

Rolling Hash: I looked into rolling hash techniques to efficiently find repeating substrings. While promising, I faced challenges in managing collisions and ensuring correctness.

What I Was Expecting:

I was hoping to find an algorithm that could efficiently handle large inputs (up to 1 million characters) and determine the longest repeating pattern in linear or near-linear time. Specifically, I expected:

Optimal Time Complexity: An algorithm with time complexity close to O(n), as opposed to quadratic or worse, which would be impractical for large inputs.

Simplicity and Practicality: A solution that is both straightforward to implement and effective for large-scale problems.