#include "testlib.h" #include #include bool isSubsequence(const std::string& sub, const std::string& str) { size_t subIndex = 0; for (size_t i = 0; i < str.length() && subIndex < sub.length(); i++) { if (sub[subIndex] == str[i]) { subIndex++; } } return subIndex == sub.length(); } int computeLCSLength(const std::string& s1, const std::string& s2) { std::vector> dp(s1.length() + 1, std::vector(s2.length() + 1, 0)); for (size_t i = 1; i <= s1.length(); i++) { for (size_t j = 1; j <= s2.length(); j++) { if (s1[i-1] == s2[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]); } } } return dp[s1.length()][s2.length()]; } int main(int argc, char* argv[]) { registerTestlibCmd(argc, argv); std::string s1 = inf.readLine(); std::string s2 = inf.readLine(); int participantLength = ouf.readInt(0, 1000, "LCS length"); if (participantLength > 0) { ouf.readEoln(); std::string participantLCS = ouf.readLine(); if (participantLCS.length() != static_cast(participantLength)) { quitf(_wa, "Reported LCS length: %d, but actual LCS string length: %zu", participantLength, participantLCS.length()); } if (!isSubsequence(participantLCS, s1)) { quitf(_wa, "Reported LCS is not a valid subsequence of the first input string"); } if (!isSubsequence(participantLCS, s2)) { quitf(_wa, "Reported LCS is not a valid subsequence of the second input string"); } } else { ouf.readEoln(); if (!ouf.eof()) { quitf(_wa, "Expected end of file after reporting LCS length of 0"); } } int correctLength = computeLCSLength(s1, s2); if (participantLength != correctLength) { quitf(_wa, "Expected LCS length: %d, found: %d", correctLength, participantLength); } quitf(_ok, "Correct"); }

코드 #1927