4 ms·
Longest common substring is linear time.
by HeliumHydride 2y ago
Longest common substring is linear time.
- terrabiped 2y agoYou may have misread the parent comment. Longest common substring is not the same type of problem as longest common subsequence.
- Xmd5a 2y agoFor those who were wondering what this means: common substring: contiguous common subsequence: not necessarily contiguous but in order
- akoboldfrying 2y agoThe 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).