Language: C++

/**
 *  最長共通部分列問題：Longest Common Subsequence probrem
 *
 *  計算量：O(n^3)
 *
 *  入力例：
 *  データセット数 　　  q
 *  文字列X           　x1
 *  文字列Y  　         y1
 *                     x2q
 *                     y2q
 *
    3
    abcbdab
    bdcaba
    abc
    abc
    abc
    bc
 *
 *  出力例：各データセットについて XX, YY の最長共通部分列 ZZ の長さ
    4
    3
    2
 *
 *
 */

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include<fstream>

#include "gtest/gtest.h"

using namespace std;
//静的領域にメモリ確保の場合のみ使用
static const int kMaxNum = 1000;

//ヒープ領域にメモリ確保の場合のみ使用
int** CreateLcsMatrix(const int s1_len, const int s2_len){
	int** lcsMatrix = new int*[s1_len + 1];
  	for(int i=0; i<=s1_len; ++i){
  		lcsMatrix[i] = new int[s2_len + 1];
  	}
  	//0初期化
    for(int row=0; row<=s1_len; ++row){
 	   for(int column=0; column<=s2_len; ++column) {
 		   lcsMatrix[row][column] = 0;
 	   }
    }
	return lcsMatrix;
}
//ヒープ領域にメモリ確保の場合のみ使用
void DeleteLcsMatrix(int** lcsMatrix, const int s1_len){
 	for(int i=0; i<=s1_len; ++i){
  		delete[] lcsMatrix[i];
  	}
 	delete[] lcsMatrix;
}

//オーバーロード lcsMatrix メモリ静的確保
int CalcLcsLength(const string& input_str1, const string& input_str2,
								const int s1_length, const int s2_length, int lcsMatrix[kMaxNum+1][kMaxNum+1]){
    const string space_str1 = ' ' + input_str1;
    const string space_str2 = ' ' + input_str2;
		/*lcsMatrix作成*/
    /** ex) abcbdab, bdcaba
     *  0 0 0 0 0 0 0
     *  0 0 0 0 1 1 2
     *  0 1 1 1 1 2 2
     *  0 1 1 2 2 2 2
     *  0 1 1 2 2 3 3
     *  0 1 2 2 2 3 3
     *  0 1 2 2 3 3 4
     *  0 1 2 2 3 4 4
     */
    for (int row = 1; row <= s1_length; row++){
        for (int column = 1; column <= s2_length; column++) {
          	//表の左上+1したものを代入
            if (space_str1[row] == space_str2[column]){
                lcsMatrix[row][column] = lcsMatrix[row - 1][column - 1] + 1;
            }
          	//表の左か上の大きい方を代入
            else{
                lcsMatrix[row][column] = max(lcsMatrix[row - 1][column], lcsMatrix[row][column - 1]);
            }
        }
    }
	return lcsMatrix[s1_length][s2_length];
}
//オーバーロード lcsMatrix vector使用
int CalcLcsLength(const string& input_str1, const string& input_str2,
								const int s1_length, const int s2_length, vector<vector<int>> lcsMatrix){
    const string space_str1 = ' ' + input_str1;
    const string space_str2 = ' ' + input_str2;
		/*lcsMatrix作成*/
    /** ex) abcbdab, bdcaba
     *  0 0 0 0 0 0 0
     *  0 0 0 0 1 1 2
     *  0 1 1 1 1 2 2
     *  0 1 1 2 2 2 2
     *  0 1 1 2 2 3 3
     *  0 1 2 2 2 3 3
     *  0 1 2 2 3 3 4
     *  0 1 2 2 3 4 4
     */
    for (int row = 1; row <= s1_length; row++){
        for (int column = 1; column <= s2_length; column++) {
          	//表の左上+1したものを代入
            if (space_str1[row] == space_str2[column]){
                lcsMatrix[row][column] = lcsMatrix[row - 1][column - 1] + 1;
            }
          	//表の左か上の大きい方を代入
            else{
                lcsMatrix[row][column] = max(lcsMatrix[row - 1][column], lcsMatrix[row][column - 1]);
            }
        }
    }
	return lcsMatrix[s1_length][s2_length];
}
//オーバーロード lcsMatrix メモリ動的確保
int CalcLcsLength(const string& input_str1, const string& input_str2,
								const int s1_length, const int s2_length, int** lcsMatrix){
    const string space_str1 = ' ' + input_str1;
    const string space_str2 = ' ' + input_str2;
		/*lcsMatrix作成*/
    /** ex) abcbdab, bdcaba
     *  0 0 0 0 0 0 0
     *  0 0 0 0 1 1 2
     *  0 1 1 1 1 2 2
     *  0 1 1 2 2 2 2
     *  0 1 1 2 2 3 3
     *  0 1 2 2 2 3 3
     *  0 1 2 2 3 3 4
     *  0 1 2 2 3 4 4
     */
    for (int row = 1; row <= s1_length; row++){
        for (int column = 1; column <= s2_length; column++) {
          	//表の左上+1したものを代入
            if (space_str1[row] == space_str2[column]){
                lcsMatrix[row][column] = lcsMatrix[row - 1][column - 1] + 1;
            }
          	//表の左か上の大きい方を代入
            else{
                lcsMatrix[row][column] = max(lcsMatrix[row - 1][column], lcsMatrix[row][column - 1]);
            }
        }
    }
	return lcsMatrix[s1_length][s2_length];
}
/**
 * lcs関数：LongestCommonSubsequence（最長共通部分列）を求める関数
 * 引数：入力文字列1,入力文字列2
 * 戻り値：最長共通部分列の長さ
 */
int lcs(const string& input_str1, const string& input_str2){
   /***************** initialize *******************/
    const int s1_length = input_str1.size();
    const int s2_length = input_str2.size();
	/***スタックオーバーフローより、静的領域またはヒープ領域にメモリ確保、またはvector使用***/
  	/**
  	 * 行(s1_length+1) × 列(s2_length+1) の行列を生成し0初期化
  	 * ex) abcbdab, bdcaba
     *  0 0 0 0 0 0 0
     *  0 0 0 0 0 0 0
     *  0 0 0 0 0 0 0
     *  0 0 0 0 0 0 0
     *  0 0 0 0 0 0 0
     *  0 0 0 0 0 0 0
     *  0 0 0 0 0 0 0
     *  0 0 0 0 0 0 0
     */
    //静的領域にメモリ静的確保
//   static int lcsMatrix[kMaxNum + 1][kMaxNum + 1] = {};
    //動的配列(vector)を使用
//	vector<vector<int>> lcsMatrix(s1_length + 1, vector<int>(s2_length + 1));
    //ヒープ領域にメモリ動的確保
  	int **lcsMatrix = CreateLcsMatrix(s1_length,s2_length);
   /***************** calculation *******************/
   //オーバーロード lcsMatrixの型が異なる可能性あり
    int lcs_val = CalcLcsLength(input_str1, input_str2, s1_length, s2_length, lcsMatrix);
    //動的確保した場合に使用
//    DeleteLcsMatrix(lcsMatrix, s1_length);

    return lcs_val;
}

void  LongestCommonSubsequenceMain(const string& input_txt) {
	std::ifstream in(input_txt);
	std::cin.rdbuf(in.rdbuf());

    /************** initialize ***************/
    string input_str1, input_str2;
    int data_set_num;
    cin >> data_set_num;
    for (int i = 0; i < data_set_num; i++){
        cin >> input_str1 >> input_str2;
        cout << lcs(input_str1, input_str2) << endl;
    }
    return;
}

TEST(AGREEMENT_TEST, agreement_test1) {
	ifstream ifs("output_txt/output0.txt");
	ASSERT_TRUE(ifs);
	string result = string(istreambuf_iterator<char>(ifs),
			istreambuf_iterator<char>());

	testing::internal::CaptureStdout();
	LongestCommonSubsequenceMain("input_txt/input0.txt");
	ASSERT_STREQ(result.c_str(),
			testing::internal::GetCapturedStdout().c_str());
}

TEST(AGREEMENT_TEST, agreement_test2) {
	ifstream ifs("output_txt/output1.txt");
	ASSERT_TRUE(ifs);
	string result = string(istreambuf_iterator<char>(ifs),
			istreambuf_iterator<char>());

	testing::internal::CaptureStdout();
	LongestCommonSubsequenceMain("input_txt/input1.txt");
	ASSERT_STREQ(result.c_str(),
			testing::internal::GetCapturedStdout().c_str());
}
TEST(AGREEMENT_TEST, agreement_test3) {
	ifstream ifs("output_txt/output2.txt");
	ASSERT_TRUE(ifs);
	string result = string(istreambuf_iterator<char>(ifs),
			istreambuf_iterator<char>());

	testing::internal::CaptureStdout();
	LongestCommonSubsequenceMain("input_txt/input2.txt");
	ASSERT_STREQ(result.c_str(),
			testing::internal::GetCapturedStdout().c_str());
}
TEST(AGREEMENT_TEST, agreement_test4) {
	ifstream ifs("output_txt/output3.txt");
	ASSERT_TRUE(ifs);
	string result = string(istreambuf_iterator<char>(ifs),
			istreambuf_iterator<char>());

	testing::internal::CaptureStdout();
	LongestCommonSubsequenceMain("input_txt/input3.txt");
	ASSERT_STREQ(result.c_str(),
			testing::internal::GetCapturedStdout().c_str());
}
TEST(AGREEMENT_TEST, agreement_test5) {
	ifstream ifs("output_txt/output4.txt");
	ASSERT_TRUE(ifs);
	string result = string(istreambuf_iterator<char>(ifs),
			istreambuf_iterator<char>());

	testing::internal::CaptureStdout();
	LongestCommonSubsequenceMain("input_txt/input4.txt");
	ASSERT_STREQ(result.c_str(),
			testing::internal::GetCapturedStdout().c_str());
}



int main(int argc, char **argv) {
	printf("Running main() from %s\n", __FILE__);
	testing::InitGoogleTest(&argc, argv);
	return RUN_ALL_TESTS();
}





Compiler output:
a.cc:35:10: fatal error: gtest/gtest.h: No such file or directory
   35 | #include "gtest/gtest.h"
      |          ^~~~~~~~~~~~~~~
compilation terminated.