Parallel algorithm vs. work in parallel

As many of the forum posts have shown, fast algorithms for solving the problem of maximal common substrings gave good results on the benchmarck but didn't really scale with the number of threads. This is because those sub-square (linear or n*logn) algorithms are hard to parallelize. Generally, when faced to such a situation one should accept the fact that the algorithm can't be parallelized and search for other approaches to make their solution scalable.