Given a string $S$ and a substring $T$, define the value of $T$ to be the total length (in characters) of all non-overlapping instances of $T$ in $S$. In other words, the value of $T$ is the length of $T$, times the number of times that $T$ occurs in $S$ without overlap.
I need an algorithm that does the following:
Given a string $S$, find the substring $T$ whose value is maximal, out of all substrings of length at least two; the index of each location where $T$ appears in $S$; and the value of $T$ (the total number of characters across all of those occurrences of $T$).
You can assume the string $S$ is ANSI encoded, where each character is one byte.
String => "AOOISDF000923RJJASPDFIJJ1023ASPD499FJJDSJIK" Has the following repetitions: 1 - "DF", two times, total characters (4) 2 - "23", two times, total characters (4) 3 - "JJ", three times, total characters (6) ... N - "ASPD", two times, total characters (8)
The desired output would be ASPD, because it has produced the largest total amount of characters (8).
Is there an efficient algorithm for this problem? Is there a search term or name for this that I could use to search for it, or papers in the literature that describe techniques for this problem?