While this is also $O(length(S))$, it requires no extra space and no recursive calls, consequently running faster in practice.

Alternatively, we can, again, take advantage of the fact that each state $v$ matches to substrings of length $[minlen(v),len(v)]$.

Since $minlen(v) = 1 + len(link(v))$ and the arimetic series formula $S[n] = n * (a[1]+a[n]) / 2$ (where $S[n]$ denotes the sum of $n$ terms,$a[1]$ representing the first term, and $a[n]$ representing the last), we can compute the length of substrings at a state in constant time. We then sum up these totals for each state $v \neq t[0]$ in the automaton. This is shown by the code below:

long long get_tot_len_diff_substings() {

long long tot{};

for(int i=1;i<sz;i++) {

long long shortest=st[st[i].link].len+1;

long long longest=st[i].len;

long long num_strings=longest-shortest+1;

long long cur=num_strings*(longest+shortest)/2;

tot += cur;

}

return tot;

}

This approaches runs in $O(length(S))$ time, but experimentally runs 20x faster than the memoized dynamic programming version on randomized strings. It requires no extra space and not recursion.