求最长公共子串长度的算法

Algorithms for Evaluating Length of the Longest Common Substring

给出求２个字符串最长公共子串（ＬＣＳ）长度的递归算法、递推算法和心动阵列算法．对２个长度分别为ｎ，ｍ（ｎ≥ｍ）的字符串，递归算法的最坏时空复杂性为（ｍ＋ｎ）！／（ｍ！ｎ！），而递推算法的时空复杂性分别仅为ｍ＋ｎｍ＋Ｏ（１），２ｍ＋Ｏ（１）．在心动阵列算法中，需ｍ个ＰＥ和ｎ＋ｍ的时间．最后给出了一个应用实例．

We give recursive, recurrence and systolic algorithms for the problem of longest common substring of two strings. For two strings with length of n and m(n≥m ), the time space complexity of the recursive algorithm in the worst case is (m+n)!/(m!n!) , time space complexity of the recurrence algorithm is m+nm+O(1) and 2m+O(1) respectively. The systolic algorithm requires m PE and m+n time units. An example of its application is also given.