最长公共子序列(LCS) 代码(C)

本文地址: http://blog.csdn.net/caroline_wendy

题目: 给定两个字符串s,t, 求出这两个字符串最长的公共子序列的长度. 字符串的子序列并一定要连续, 能够包含间隔.

即最长公共子序列问题(LCS, Longest Common Subsequence)

使用动态规划, 假设字符相等, 两个字符串就依次递增一位, 一直到字符串的结尾.

代码:

/* * main.cpp * *  Created on: 2014.7.17 *      Author: spike *//*eclipse cdt, gcc 4.8.1*/#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           using namespace std;class Program { static const int MAX_N = 100; int n=4, m=4; char s[MAX_N] = "abcd", t[MAX_N] = "becd"; int dp[MAX_N+1][MAX_N+1];public: void solve() { for (int i=0; i
          
         
        
       
      
     

输出:

result = 3