3 ms·
You may have misread the parent comment. Longest common substring is not the same type of problem as longest common subsequence.
by terrabiped 2y ago
You 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).