題目連結 http://www.tcgs.tc.edu.tw:1218/ShowProblem?problemid=b033。
此題用 Dynamic Programming ,可參考 https://en.wikipedia.org/wiki/Longest_common_subsequence_problem#Computing_the_length_of_the_LCS 。
演算法(底下文字是從https://en.wikipedia.org/wiki/Longest_common_subsequence_problem#Computing_the_length_of_the_LCS 節錄出來)
程式碼:
- #include <iostream>
- #include <cstring>
- #include <vector>
- using namespace std;
- int lengthOfLCS(string x, int m, string y, int n) {
- int C[m+1][n+1];
- for(int i = 0; i <= m; i++)
- {
- for(int j = 0; j <= n; j++)
- {
- if(i == 0 || j == 0)
- C[i][j] = 0;
- else if(x[i-1] == y[j-1])
- C[i][j] = C[i-1][j-1] + 1;
- else
- C[i][j] = max(C[i][j-1], C[i-1][j]);
- }
- }
- return C[m][n];
- }
- int main()
- {
- string a, b;
- cin >> a >> b;
- cout << lengthOfLCS(a, a.length(), b, b.length());
- return 0;
- }
沒有留言:
張貼留言