LCS 教学篇

LCS就是最长公共子序列

比如两个串为：

abcicba
abdkscab

ab是两个串的子序列，abc也是，abca也是，其中abca是这两个字符串最长的子序列。

对于LCS的求法，首先可以想到暴力枚举字符串1的每一位，再去匹配字符串2的每一位，这样的复杂度明显很高，不适用长度太大的字符串。

那么我们可以考虑用一个二维矩阵dp[][]，dp[i][j]储存str1的前i项和str2前j项的LCS，当str1[i]==str2[j]的时候，假设dp[i-1][j-1]已经求出，那dp[i][j]肯定是dp[i-1][j-1]+1。如果str1[i]！=str2[j]，因为我们求的是子序列，要把之前的关系传递下来，所以dp[i][j]=max(dp[i][j-1], dp[i-1][j])。这样就完成LCS了，dp[lenstr1][lenstr2]就是LCS的长度，那么我们又要怎么输出这串LCS呢。我们先看一下dp存的内容。

假设

str1 = abcicba

str2 = abdkscab

dp[][]则为

1 1 1 1 1 1 1 1
1 2 2 2 2 2 2 2
1 2 2 2 2 3 3 3
1 2 2 2 2 3 3 3
1 2 2 2 2 3 3 3
1 2 2 2 2 3 3 4
1 2 2 2 2 3 4 4

其实LCS求的也是最长主对角线，那么我们从x=lenstr1，y=lenstr2开始找对角线。我们考虑，在处理dp时，如果str1[i]==str2[j]，dp[i][j]=dp[i-1][j-1]+1,这个时候dp[i-1][j]和dp[i][j-1]一定不等于dp[i][j]的，所以我们要找到dp[x][y]!=dp[x-1][y]&&dp[x][y]!=dp[x][y-1]的地方，输出str1[x]或者str2[y]，如果不满足条件，则继续往和dp[x][y]相同的位置找。因为寻找是倒着找的，所以直接输出也会是倒着的，可以考虑用递归写一发。

对于上面的字符串，输出大概是这么遍历的：（数字代表遍历次序）

11 0 0 0 0 0 0 0
1 10 9 8 7 0 0 0
0 0 0 0 0 6 5 0
0 0 0 0 0 0 4 0
0 0 0 0 0 0 3 0
0 0 0 0 0 0 0 2
0 0 0 0 0 0 0 1

51nod有题目，可以做一下：http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1006

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <string>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#define X first
#define Y second
#define clr(u,v); memset(u,v,sizeof(u));
#define in() freopen("data","r",stdin);
#define out() freopen("ans","w",stdout);
#define Clear(Q); while (!Q.empty()) Q.pop();
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 1e3 + 10;
const int INF = 0x3f3f3f3f;
char str1[maxn], str2[maxn];
int dp[maxn][maxn];
void print(int i, int j)//输出函数
{
    if (i == 0 || j == 0) return ;
    if (dp[i-1][j] == dp[i][j]) print(i - 1, j);
    else if (dp[i][j-1] == dp[i][j]) print(i, j - 1);
    else
    {
        print(i - 1, j - 1);
        putchar(str1[i]);
    }
}
int main()
{
    scanf("%s%s", str1 + 1, str2 + 1);
    int len1 = strlen(str1 + 1), len2 = strlen(str2 + 1);
    for (int i = 1; i <= len1; i++)
        for (int j = 1; j <= len2; j++)
        {
            if (str1[i] == str2[j]) dp[i][j] = dp[i-1][j-1] + 1;
            else dp[i][j] = max(dp[i][j-1], dp[i-1][j]);
        }
//    for (int i = 1; i <= len1; i++)
//    {
//        for (int j = 1; j <= len2; j++)
//            printf("%d ", dp[i][j]);
//        puts("");
//    }
    print(len1, len2);
    return 0;
}