算法LCS,所有的最长公共子序列

所有的最长公共子序列 LCS 一 问题描述 子序列的概念子序列的概念 设设 X 若有 若有 1 i1 i2 ik m 得 得 Z 则称则称 Z 是是 X 的子序列 记为的子序列 记为 Z X e g X Z 则有则有 Z X 公共子序列的概念 公共子序列的概念 设设 X Y 是两个序列 且是两个序列 且有有 Z X 和和 Z Y 则称 则称 Z 是是 X 和和 Y 的公共的公共 列 列 最长公共子序列的概念最长公共子序列的概念 若若 Z X Z Y 且且不存在比不存在比 Z 更长的更长的 X 和和 Y 的公共子序列的公共子序列 则称则称 Z 是是 X 和和 Y 的最长公共子序列 记为的最长公共子序列 记为 Z LCS X Y 但是但是 LCS 不是只有一个 不是只有一个 最长公共子序列往往不止一个最长公共子序列往往不止一个 e g X Y 则 Z Z Z 均属于 LCS X Y 即 X Y 有 3 个 LCS 本文描述如何寻找所有的 LCS 二 问题分析 先描述寻找一个 LCS 的思想 记记 Xi x1 xi 即即 X 序列的前序列的前 i 个字符个字符 1 i m 前缀 前缀 Yj y1 yj 即即 Y 序列的前序列的前 j 个字符个字符 1 j n 前缀 前缀 假定假定 Z z1 zk LCS X Y 若若 xm yn 最后一个字符相同 最后一个字符相同 则不难用反证法证明 则不难用反证法证明 该字符必是该字符必是 X 与与 Y 的的任一任一最长公共子序列最长公共子序列 Z 设长度为 设长度为 k 的最后 的最后 一个字符 即有一个字符 即有 zk xm yn 且显然有 且显然有 Zk 1 LCS Xm 1 Yn 1 即即 Z 的前缀的前缀 Zk 1是是 Xm 1与与 Yn 1的最长公共子序列 的最长公共子序列 若若 xm yn 则亦不难用反证法证明 则亦不难用反证法证明 要么要么 Z LCS Xm 1 Y 要么 要么 Z LCS X Yn 1 由于 由于 zk xm与与 zk yn 其中至少有一个必成立 因此 若其中至少有一个必成立 因此 若 zk xm则有则有 Z LCS Xm 1 Y 若 若 zk yn 则有则有 Z LCS X Yn 1 若若 xm yn 则问题化归成求 则问题化归成求 Xm 1与与 Yn 1的的 LCS LCS X Y 的长的长 度等于度等于 LCS Xm 1 Yn 1 的长度加的长度加 1 若若 xm yn 则问题化归成求 则问题化归成求 Xm 1与与 Y 的的 LCS 及及 X 与与 Yn 1的的 LCSLCS X Y 的长度为 的长度为 Max LCS Xm 1 Y 的长度的长度 LCS X Yn 1 的的 长度长度 求求 LCS Xm 1 Y 的长度与的长度与 LCS X Yn 1 的长度这两个问题不是相互的长度这两个问题不是相互 独立的 独立的 两者都需要求两者都需要求 LCS Xm 1 Yn 1 的长度的长度 因而因而具有重叠性具有重叠性 此外 此外 两个序列的两个序列的 LCS 中包含了两个序列的前缀的中包含了两个序列的前缀的 LCS 故问题故问题具有最优子结构性质具有最优子结构性质 考虑用动态规划法 考虑用动态规划法 引进一个二维数组引进一个二维数组 C 用用 C i j 记录记录 Xi与与 Yj的的 LCS 的长度的长度 如果我们是如果我们是按行 列的序号从小到大地进行递推计算按行 列的序号从小到大地进行递推计算 从第 从第 1 行开始计算 行开始计算 C 1 1 C 1 2 C 1 n 再算再算 C 2 1 C 2 2 C 2 n 最后计算 最后计算 C m 1 C m 2 C m n 最后算出的 最后算出的 C m n 即即 为为 LCS X Y 的长度 的长度 那么 那么在计算在计算 C i j 之前 之前 C i 1 j 1 C i 1 j 与与 C i j 1 均已计算出来均已计算出来 此时 此时 根据根据 X i Y j 还是还是 X i Y j 就可以计算出 就可以计算出 C i j 若若 X i Y j 则执行 则执行 C i j C i 1 j 1 1 若若 X i Y j 进行下述判断 进行下述判断 若若 C i 1 j C i j 1 则则 C i j 取取 C i 1 j 否则否则 C i j 取取 C i j 1 即有 即有 C i j y x y x j i j i jijiCjiC jijiC ji 且若 且若 或若 0 1 1 max 0 1 1 1 000 为了构造出为了构造出 LCS 使用一个 使用一个 m n 的二维数组的二维数组 b b i j 记录记录 C i j 是通过哪一个子问题的值求得的是通过哪一个子问题的值求得的 以决定搜索的方向 以决定搜索的方向 若若 X i Y j 则 则 b i j 中记入中记入 亦可不记亦可不记 若若 X i Y j 且且 C i 1 j C i j 1 则 则 b i j 中记入中记入 若若 X i Y j 且且 C i 1 j C i j 1 则 则 b i j 中记入中记入 e g 对于对于 X Y 求出的各个求出的各个 C i j 与与 b i j 如下图 如下图 0 1 2 3 4 5 6 yj B D C A B A 0 xi 0 0 0 0 0 0 0 1 A 0 0 00 1 1 1 2 B 0 1 1 1 1 2 2 3 C 0 1 1 2 2 2 2 4 B 0 1 1 2 2 3 3 5 D 0 1 22 2 3 3 6 A 0 1 22 33 4 7 B 0 1 22 3 4 4 找出所有路径的思想 仅用仅用 是搜索不到所有的是搜索不到所有的 LCS 的 因为的 因为 C i 1 j C i j 1 我们没有区分 我们没有区分 C i 1 j C i j 1 还是还是 C i 1 j C i j 1 此时我们只是在单方向搜索 就像是图的深度优先搜索 走到此时我们只是在单方向搜索 就像是图的深度优先搜索 走到 底 找出一条路径 为了找出所有的底 找出一条路径 为了找出所有的 LCS 我们将 我们将 C i 1 j C i j 1 记做记做 同时用遍历同时用遍历 b i j 构造出一棵树构造出一棵树 tree 的方向记做节点的左子的方向记做节点的左子 树 右子树为空 树 右子树为空 的方向记做节点的右子树 左子树为空 的方向记做节点的右子树 左子树为空 的的 方向开辟新的节点 并对其赋值 方向开辟新的节点 并对其赋值 记做节点的左子树和右子记做节点的左子树和右子 树 当树构造完毕时 我们从叶子节点开始遍历 一直到根为止 树 当树构造完毕时 我们从叶子节点开始遍历 一直到根为止 即找出所有的即找出所有的 LCS 注意 此时找出的所有的注意 此时找出的所有的 LCS 可能有重复的 所以用一个字符可能有重复的 所以用一个字符 串数组来记录不同的串数组来记录不同的 LCS 容易证明该字符数组最长为 容易证明该字符数组最长为 min x length y length 三 解决方案三 解决方案 为了方便 程序中将为了方便 程序中将 记做记做 1 记做记做 1 记做记做 0 记做记做 2 treenode h ifndef TREENODE H define TREENODE H class TreeNode friend class tree public TreeNode char a 0 构造函数构造函数 data a leftchild 0 rightchild 0 parent 0 TreeNode leftchild TreeNode rightchild TreeNode parent 从叶子往根遍历时找的路线从叶子往根遍历时找的路线 char data endif 构造树构造树 tree h ifndef TREE H define TREE H include treenode h include include stack h const int m 7 n 6 默认默认 x 的长度为的长度为 7 y 的长度为的长度为 6 int i 0 j 0 int exsit 0 记录字符串数组有几个元素记录字符串数组有几个元素 class tree public tree int b m 1 n 1 string x int i int j TreeNode LCS int b m 1 n 1 string x int i int j 构造树构造树 void inorder void inorder TreeNode 中序遍历 找出所有的叶子节点中序遍历 找出所有的叶子节点 void con parent 遍历树 找出每个节点的遍历树 找出每个节点的 parent void tranverse TreeNode 从叶子节点遍历到根 找出从叶子节点遍历到根 找出 LCS void output 输出所有的输出所有的 LCS private TreeNode root 根根 Stack stack 用栈来记录叶子节点用栈来记录叶子节点 string t 字符串数组记录不同的字符串数组记录不同的 LCS tree tree int b m 1 n 1 string x int i int j t new string n 字符串数组最长为字符串数组最长为 min x length y length for int y 0 yleftchild LCS b x i 1 j 1 左子树继续构造左子树继续构造 return a else if b i j 1 return LCS b x i 1 j 往上面走 不创造新节点 继续递归往上面走 不创造新节点 继续递归 else if b i j 1 return LCS b x i j 1 往左面走 不创造新节点 继续递归往左面走 不创造新节点 继续递归 else 遇到两个方向的点 创造新节点 并默认赋值为遇到两个方向的点 创造新节点 并默认赋值为 递归构造递归构造左子树和右左子树和右 子树 子树 TreeNode a new TreeNode a leftchild LCS b x i 1 j a rightchild LCS b x i j 1 return a void tree inorder inorder root 找出所有的叶子节点用栈来记录找出所有的叶子节点用栈来记录 void tree inorder TreeNode current if current inorder current leftchild if current data stack add current inorder current rightchild 遍历树 找出每个节点的遍历树 找出每个节点的 parent void tree con parent int i 0 Stack s TreeNode currentNode root while 1 while currentNode s add currentNode TreeNode pp currentNode if currentNode leftchild currentNode leftchild parent pp currentNode currentNode leftchild if s IsEmpty return currentNode s Top cout data rightchild currentNode rightchild parent pp currentNode currentNode rightchild 从叶子遍历到根 找出从叶子遍历到根 找出 LCS void tree tranverse TreeNode leaf TreeNode currentNode leaf string temp bool flag true while currentNode parent if currentNode data currentNode currentNode parent if root data 若根有非真值添加到其中去若根有非真值添加到其中去 temp root data 看看 LCS 若有重复的 不存入若有重复的 不存入 string 数组中 数组中 for int count 0 count m count if temp t count flag false break if flag cout temp n t exsit temp temp flag true 找出所有的找出所有的 LCS void tree output while stack IsEmpty tranverse stack Top endif test cpp 测试函数测试函数 include using namespace std include tree h