<commit_before>---
layout: post
title: "最长公共子序列问题"       # Title of the post
subtitle:
date:       2017-03-13 17:00:00
author:     "随机漫步的傻瓜"
header-img: "img/post-bg-2015.jpg"
catalog: true
tags:
    - 数据结构与算法
---
## 最长公共子序列与最长公共子串的区别

- 子序列是有序的，但不一定是连续，作用对象是序列
- 子串是有序且连续的，作用对象是字符串

## 基本思想
![最长公共子序列](/img/最长公共子序列.png)

## C++程序实现<commit_msg>添加C++程序<commit_after>---
layout: post
title: "最长公共子序列问题"       # Title of the post
subtitle:
date:       2017-03-13 17:00:00
author:     "随机漫步的傻瓜"
header-img: "img/post-bg-2015.jpg"
catalog: true
tags:
    - 数据结构与算法
---
## 最长公共子序列与最长公共子串的区别

- 子序列是有序的，但不一定是连续，作用对象是序列
- 子串是有序且连续的，作用对象是字符串

## 基本思想
![最长公共子序列](/img/最长公共子序列.png)

## C++程序实现
```c++
#include <iostream>
using namespace std;

int lcs(string X,string Y)
{
    auto m=X.length();
    auto n=X.length();
    int L[m+1][n+1];
    for(int i=0;i<=m;i++)
        for(int j=0;j<=n;j++)
        {
            if(i==0||j==0)
                L[i][j]=0;
            else if(X[i-1]==Y[j-1])
                L[i][j]=L[i-1][j-1]+1;
            else
                L[i][j]=(L[i-1][j]>L[i][j-1])?L[i-1][j]:L[i][j-1];
        }
    return L[m][n];
}

int main()
{
    string X="AGGTAB";
    string Y="GXTXAYB";
    cout<<"Length of LCS is:"<<lcs(X,Y);
    cout<<endl;
    return 0;
}
```
{'fraction_non_alphanumeric': 0.2084639498432602, 'fraction_numerical': 0.041536050156739814, 'mean_word_length': 2.527624309392265, 'pattern_counts': {'":': 0, '<': 12, '<?xml version=': 0, '>': 5, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '4325257', 'n_tokens_mistral': 737, 'n_tokens_neox': 754, 'n_words': 95}