数据结构——堆排序

LCS最长公共子序列

  一类问题的主体是：给定两个字符序列，形如str1=a1,a2...,ai;$str1=a_1,a_2...,a_i;$ str2=b1.b2...,bj.$str2=b_1.b_2...,b_j.$寻找其中最长的相同子串。这里的子串不必要连续。
  这样的问题就是寻找最长公共子序列。
  这样的问题可以从动态规划思想入手，可以知道如果需要求LCS(i,j)，就是串str1(0:i)$str1(0:i)$和str2(0:j)$str2(0:j)$的最长公共子序列。若str[i]=str[j],那么LCS(i,j)=LCS(i-1,j-1)+1,否则LCS(i,j)=max(LCS(i-1,j),LCS(i,j-1));

common Subsequence POJ - 1458
这是一个模板LCS题目：

#include <iostream>
#include <cstdio>
#include <cstring>
#define Mem(a,b) memset(a,b,sizeof(a))
#define For(a,b,c) for(int a=b;a<c;a++)

using namespace std;
const int maxn = 1e5+5;
string s1,s2;
int dp[2][maxn];
int main()
{
    while(cin>>s1>>s2)
    {
        Mem(dp,0);
        int alen=s1.length(),
        blen=s2.length();
        int k=0,kk=1;
        For(i,0,alen)
        {

            For(j,0,blen)
            {

                if(s1[i]==s2[j])
                    dp[k][j+1] = dp[!k][j]+1;
                else
                    dp[k][j+1] = max(dp[!k][j+1],dp[k][j]);
            }
            k=!k;
        }
        printf("%d\n",dp[!k][blen]);
    }
    return 0;
}