最長公共子序列

時間限制：3000?ms ?|? 內存限制：65535?KB 難度：3 描述

咱們就不拐彎抹角了，如題，需要你做的就是寫一個程序，得出最長公共子序列。
tip：最長公共子序列也稱作最長公共子串(不要求連續)，英文縮寫為LCS（Longest Common Subsequence）。其定義是，一個序列 S ，如果分別是兩個或多個已知序列的子序列，且是所有符合此條件序列中最長的，則 S 稱為已知序列的最長公共子序列。

輸入

第一行給出一個整數N(0<N<100)表示待測數據組數
接下來每組數據兩行，分別為待測的兩組字符串。每個字符串長度不大于1000.

輸出

每組測試數據輸出一個整數，表示最長公共子序列長度。每組結果占一行。

樣例輸入

2 asdf adfsd 123abc abc123abc

樣例輸出

3 6

?

?

思路：動態規劃，不是KMP!!!

?

?

?

?

#include <iostream> #include <string> #include <cstdio>using namespace std;int martix[1000][1000] = {0};int main(){int n;cin>>n;while (n--){string a,b;cin>>a>>b;int i,j;for (i = 1; i <= a.length(); i++){for (j = 1; j <= b.length(); j++){if (a[i-1]==b[j-1]){martix[i][j] = martix[i-1][j-1] + 1;}else{if (martix[i][j-1] > martix[i-1][j]){martix[i][j] = martix[i][j-1];}else{martix[i][j] = martix[i-1][j];}}}}cout<<martix[a.length()][b.length()]<<endl;}return 0;}

?

轉載于:https://www.cnblogs.com/lyc94620/p/9289280.html

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的【ACM】最长公共子序列 - 动态规划的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。