#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
// Function to find the longest common subsequence
std::string findLCS(const std::string& str1, const std::string& str2) {
int m = str1.length();
int n = str2.length();
// Create a 2D vector to store the LCS lengths
std::vector<std::vector<int>> dp(m + 1, std::vector<int>(n + 1, 0));
// Fill the dp table
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (str1[i - 1] == str2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = std::max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
// Reconstruct the LCS string
std::string lcs;
int i = m, j = n;
while (i > 0 && j > 0) {
if (str1[i - 1] == str2[j - 1]) {
lcs = str1[i - 1] + lcs;
i--;
j--;
} else if (dp[i - 1][j] > dp[i][j - 1]) {
i--;
} else {
j--;
}
}
return lcs;
}
// Function to find the longest common substring
std::string findLCSubstr(const std::string& str1, const std::string& str2) {
int m = str1.length();
int n = str2.length();
int maxLen = 0;
int endingIndex = 0;
// Create a 2D vector to store the lengths of common substrings
std::vector<std::vector<int>> dp(m + 1, std::vector<int>(n + 1, 0));
// Fill the dp table
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (str1[i - 1] == str2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
if (dp[i][j] > maxLen) {
maxLen = dp[i][j];
endingIndex = i;
}
}
}
}
// Extract the longest common substring
return str1.substr(endingIndex - maxLen, maxLen);
}
int main() {
std::string str1, str2;
int choice;
do {
std::cout << "Enter two strings (or 'q' to quit): ";
std::getline(std::cin, str1);
if (str1 == "q") {
break;
}
std::getline(std::cin, str2);
std::cout << "Choose an option:\n";
std::cout << "1. Find the longest common subsequence\n";
std::cout << "2. Find the longest common substring\n";
std::cout << "Enter your choice: ";
std::cin >> choice;
std::cin.ignore(); // Ignore the newline character
switch (choice) {
case 1: {
std::string lcs = findLCS(str1, str2);
std::cout << "The longest common subsequence is: " << lcs << " (Length: " << lcs.length() << ")\n";
break;
}
case 2: {
std::string lcSubstr = findLCSubstr(str1, str2);
std::cout << "The longest common substring is: " << lcSubstr << " (Length: " << lcSubstr.length() << ")\n";
break;
}
default:
std::cout << "Invalid choice. Please try again.\n";
break;
}
std::cout << "\n";
} while (str1 != "q");
return 0;
} Write, Run & Share C++ code online using OneCompiler's C++ online compiler for free. It's one of the robust, feature-rich online compilers for C++ language, running on the latest version 17. Getting started with the OneCompiler's C++ compiler is simple and pretty fast. The editor shows sample boilerplate code when you choose language as C++ and start coding!
OneCompiler's C++ online compiler supports stdin and users can give inputs to programs using the STDIN textbox under the I/O tab. Following is a sample program which takes name as input and print your name with hello.
#include <iostream>
#include <string>
using namespace std;
int main()
{
string name;
cout << "Enter name:";
getline (cin, name);
cout << "Hello " << name;
return 0;
}
C++ is a widely used middle-level programming language.
When ever you want to perform a set of operations based on a condition If-Else is used.
if(conditional-expression) {
//code
}
else {
//code
}
You can also use if-else for nested Ifs and If-Else-If ladder when multiple conditions are to be performed on a single variable.
Switch is an alternative to If-Else-If ladder.
switch(conditional-expression){
case value1:
// code
break; // optional
case value2:
// code
break; // optional
......
default:
code to be executed when all the above cases are not matched;
}
For loop is used to iterate a set of statements based on a condition.
for(Initialization; Condition; Increment/decrement){
//code
}
While is also used to iterate a set of statements based on a condition. Usually while is preferred when number of iterations are not known in advance.
while (condition) {
// code
}
Do-while is also used to iterate a set of statements based on a condition. It is mostly used when you need to execute the statements atleast once.
do {
// code
} while (condition);
Function is a sub-routine which contains set of statements. Usually functions are written when multiple calls are required to same set of statements which increases re-usuability and modularity. Function gets run only when it is called.
return_type function_name(parameters);
function_name (parameters)
return_type function_name(parameters) {
// code
}