> only non-bruteforce solution worth pursuing here involves DP

What's wrong with starting with a hashtable of substrings of fixed length? For inputs with low autocorrelation, that'll get you a good average-case speed up.