Share xâu con chung dài nhất c++,

[minhanhcartoon]

#Chất nền chung nhất, #C ++, #String, #AlGorithM ## Chất nền chung dài nhất trong C ++

Chất nền chung dài nhất (LCS) của hai chuỗi là chuỗi con dài nhất xuất hiện trong cả hai chuỗi.Ví dụ, chuỗi con chung dài nhất của các chuỗi "ABCBDAB" và "BDCABA" là "BCBA".

Tìm chất nền chung dài nhất là một vấn đề cổ điển trong khoa học máy tính.Có một số thuật toán khác nhau để giải quyết vấn đề này, mỗi thuật toán có ưu điểm và nhược điểm riêng.

Một thuật toán đơn giản để tìm ra chuỗi con chung dài nhất là thuật toán vũ lực.Thuật toán này chỉ đơn giản là so sánh mọi chuỗi con của một chuỗi với mỗi chuỗi con của chuỗi khác và trả về chuỗi con dài nhất khớp với cả hai chuỗi.Độ phức tạp về thời gian của thuật toán này là O (n^2), trong đó n là chiều dài của chuỗi dài hơn.

Một thuật toán hiệu quả hơn để tìm ra chuỗi con chung dài nhất là thuật toán lập trình động.Thuật toán này hoạt động bằng cách xây dựng một bảng độ dài của các phần phụ dài nhất của tiền tố của hai chuỗi.Chất nền chung dài nhất sau đó có thể được tìm thấy bằng cách tìm mục dài nhất trong bảng này.Độ phức tạp về thời gian của thuật toán này là O (n*m), trong đó n là độ dài của chuỗi thứ nhất và m là độ dài của chuỗi thứ hai.

Sau đây là việc triển khai thuật toán lập trình động để tìm bộ nền chung dài nhất trong C ++:

`` `C ++
#include <Istream>
#include <String>

sử dụng không gian tên STD;

// Trả về chiều dài của chuỗi con chung dài nhất của chuỗi S1 và S2.
int longestCommonsubString (Chuỗi S1, Chuỗi S2) {
// Tạo một bảng để lưu trữ độ dài của các chuỗi con chung dài nhất của các tiền tố của S1 và S2.
int n = s1.length ();
int m = s2.length ();
Bảng int [n + 1] [m + 1];

// Khởi tạo bảng.
for (int i = 0; i <= n; i ++) {
for (int j = 0; j <= m; j ++) {
Bảng [j] = 0;
}
}

// Điền vào bảng.
for (int i = 1; i <= n; i ++) {
for (int j = 1; j <= m; j ++) {
if (s1 [i - 1] == s2 [j - 1]) {
Bảng [j] = Bảng [i - 1] [j - 1] + 1;
} khác {
Bảng [j] = max (bảng [i - 1] [j], bảng [j - 1]);
}
}
}

// Trả về chiều dài của chuỗi con chung dài nhất.
Bảng trở lại [n] [m];
}

int main () {
// Nhận hai chuỗi từ người dùng.
Chuỗi S1, S2;
cout << "Nhập chuỗi đầu tiên:";
CIN >> S1;
cout << "Nhập chuỗi thứ hai:";
CIN >> S2;

// Tìm chuỗi con chung dài nhất.
int length = longestCommonsubString (S1, S2);

// In các chuỗi con chung dài nhất.
cout << "Chất nền chung dài nhất là:" << s1.substr (s1.length () - chiều dài, độ dài) << endl;

trả lại 0;
}
`` `

## hashtags

* #Chất nền chung nhất
* #C ++
* #sợi dây
* #AlGorithM
* #lập trình năng động
=======================================
#Longest common substring, #C++, #String, #AlGorithM ## The Longest Common Substring in C++

The longest common substring (LCS) of two strings is the longest substring that appears in both strings. For example, the longest common substring of the strings "ABCBDAB" and "BDCABA" is "BCBA".

Finding the longest common substring is a classic problem in computer science. There are a number of different algorithms for solving this problem, each with its own advantages and disadvantages.

One simple algorithm for finding the longest common substring is the brute-force algorithm. This algorithm simply compares every substring of one string to every substring of the other string, and returns the longest substring that matches in both strings. The time complexity of this algorithm is O(n^2), where n is the length of the longer string.

A more efficient algorithm for finding the longest common substring is the dynamic programming algorithm. This algorithm works by building up a table of the lengths of the longest common substrings of prefixes of the two strings. The longest common substring can then be found by finding the longest entry in this table. The time complexity of this algorithm is O(n*m), where n is the length of the first string and m is the length of the second string.

The following is an implementation of the dynamic programming algorithm for finding the longest common substring in C++:

```c++
#include <iostream>
#include <string>

using namespace std;

// Returns the length of the longest common substring of the strings s1 and s2.
int longestCommonSubstring(string s1, string s2) {
// Create a table to store the lengths of the longest common substrings of prefixes of s1 and s2.
int n = s1.length();
int m = s2.length();
int table[n + 1][m + 1];

// Initialize the table.
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= m; j++) {
table[j] = 0;
}
}

// Fill in the table.
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (s1[i - 1] == s2[j - 1]) {
table[j] = table[i - 1][j - 1] + 1;
} else {
table[j] = max(table[i - 1][j], table[j - 1]);
}
}
}

// Return the length of the longest common substring.
return table[n][m];
}

int main() {
// Get the two strings from the user.
string s1, s2;
cout << "Enter the first string: ";
cin >> s1;
cout << "Enter the second string: ";
cin >> s2;

// Find the longest common substring.
int length = longestCommonSubstring(s1, s2);

// Print the longest common substring.
cout << "The longest common substring is: " << s1.substr(s1.length() - length, length) << endl;

return 0;
}
```

## Hashtags

* #Longest common substring
* #C++
* #String
* #AlGorithM
* #Dynamic programming