Sort all suffixes, then binary-search the answer. For a candidate length $l$, group the sorted suffixes so that every group has lcp(height) at least $l$. Within each group, track the maximum and minimum of rl(sa); if their difference exceeds $l$, a non-overlapping repeated substring of length $l$ exists. This is $O(n \log n)$. You can also do it in $O(n)$ by using two pointers together with a monotonic deque to maintain the max/min of rl(sa); the answer is the largest lcp(height) seen across valid groups.

The same binary-search-on-$l$ approach works: check whether some group with lcp(height) >= l contains at least $k$ suffixes. That’s $O(n \log n)$. It also runs in $O(n)$ with two pointers by sliding a window of exactly $k$ consecutive suffixes.

Notice that for the suffix ranked $i$-th, all substrings starting at rl[i] and ending at or before lcp[i] characters into the suffix would be double-counted. Subtracting those out, the answer is $\sum_{i=1}^{n} \bigl(n - rl[i] + 1 - lcp[i]\bigr),$ computable in $O(n)$.

Reverse the string, concatenate it to the original with an unused separator in the middle, then run suffix array on the combined string. Enumerate center points (splitting into odd/even-length cases) and combine with $ST$-table range-min on the height array. Precomputation is $O(n \log n)$; querying is $O(1)$, so total $O(n \log n)$. If you replace the $ST$ table with Cartesian tree + Tarjan for $O(1)$ RMQ with $O(n)$ preprocessing, the whole solution becomes $O(n)$.

Observation: if a string is the concatenation of $k$ copies of a period of length $l$, then $lcp(s[1], s[l+1]) = n - l$. Enumerate the divisors of $n$ and use the $ST$-table to check the $lcp$; that’s $O(n \log n)$. If you notice that one endpoint of the RMQ is always fixed, you can precompute in $O(n)$ and drop the $\log$.

Enumerate period length $l$. For any candidate period, positions $s[1], s[1+l], \dots, s[1+xl]$ must fall inside a run of length-$l$ repeats. For adjacent samples $s[1 + al]$ and $s[1 + al + l]$, their $lcp$ gives the maximum stretch to the right; if $lcp$ isn’t a multiple of $l$, check whether pushing the start one step to the left adds one more copy. The complexity works out to $O\!\left(\sum_{i=1}^{n} \frac{n}{i}\right) = O(n \log n).$

Concatenate the two strings with an unused separator, then run suffix array on the combined string. The longest common substring must appear as the $lcp$ of two adjacent suffixes that come from different original strings. $O(n)$.

Concatenate as above and run suffix array. For each suffix of $B$, count contributions from previously seen suffixes of $A$, then swap roles and do the same. A monotonic stack keeps the running sum in $O(1)$ amortized per suffix, giving $O(n)$ overall.

Concatenate all strings using $k$ distinct unused separators, then run suffix array. Binary-search the length $l$: for each contiguous group with lcp >= l, check whether the group spans at least $k$ different source strings. $O(n \log n)$. As before, two pointers + a monotonic deque bring this down to $O(n)$.

Same concatenation trick, then binary-search $l$. For each lcp >= l group, per source string track the max and min rl and check that every string has two occurrences that don’t overlap. $O(n \log n)$.

For every string, append its reverse and use $2n$ distinct unused separators between the pieces. Run suffix array on the combined string, then binary-search $l$ and check whether each group covers every original string. Also $O(n \log n)$.