Parallel algorithms for the longest common subsequence problem

摘要

The longest common subsequence problem is to find a substring that is common to two given strings and is at least as long as any other such string. If m and n are the lengths of the two strings (m2), we obtain O(log m) time parallel algorithm with mn processors and an O(log/sup 2/ n) time optimal parallel algorithm. Serial complexity on the decision tree model is /spl Theta/(mn).