[terrabiped]

You may have misread the parent comment. Longest common substring is not the same type of problem as longest common subsequence.

[Xmd5a]

For those who were wondering what this means:

    common substring: contiguous
    common subsequence: not necessarily contiguous but in order

[akoboldfrying]

The post you responded to is merely giving evidence that the GP's overall claim "Any of these text problems where you're tying to optimize over a whole corpus is kind of not hard to see to be NP-complete" is sometimes not true in surprising ways -- Knuth conjectured that there was no linear time algorithm for longest common substring (but then suffix trees came along).