轉:最長公共子串和最長公共子序列的差別

一、什麼是最長公共子序列         什麼是最長公共子序列呢？舉個簡單的例子吧，一個數列S，若分别是兩個或多個已知序列的子序列，且是所有符合條件序列中最長的，則S稱為已知序列的最長公共子序列。

  舉例如下，如：有兩個随機數列，1 2 3 4 5 6 和 3 4 5 8 9，則它們的最長公共子序列便是：3 4 5。

  一直不明白：最長公共子串和最長公共子序列的差別。       上網查了下，最長公共子串（Longest Common Substirng）和最長公共子序列（Longest Common Subsequence，LCS）的差別為：子串是串的一個連續的部分，子序列則是從不改變序列的順序，而從序列中去掉任意的元素而獲得新的序列；也就是說，子串中字元的位置必須是連續的，子序列則可以不必連續。

二、蠻力法

   蠻力法是解決最長公共子序列問題最容易想到的方法，即對S的每一個子序列，檢查是否為T的子序列，進而确定它是否為S和T的公共子序列，并且選出最長的公共子序列。      S和T的所有子序列都檢查過後即可求出S和T的最長公共子序列。S的一個子序列相應于下标序列1,2，...，n的一個子序列。是以，S共有2^n個子序列。當然，T也有2^m個子序列。

   是以，蠻力法的時間複雜度為O(2^n * 2^m)，這可是指數級别的啊。