#include #include #include #include #define MAXN 105 using namespace std; int dp[MAXN][MAXN], path[MAXN][MAXN]; int LCS(string &s1, string &s2, int n){ int i, j; for (i = 0; i <= n; i++) dp[i][0] = dp[0][i] = 0; for (i = 1; i <=n; i++){ for (j = 1; j <= n; j++){ if (s1[i - 1] == s2[j - 1]) dp[i][j] = 1 + dp[i - 1][j - 1], path[i][j] = 1; else if (dp[i - 1][j] > dp[i][j - 1]) dp[i][j] = dp[i - 1][j], path[i][j] = 2; else dp[i][j] = dp[i][j - 1], path[i][j] = 3; } } return dp[n][n]; } void printResult(string &s, int i, int j){ if (!i) return; switch (path[i][j]){ case 1: cout << s[i-1]; printResult(s, i - 1, j - 1); break; case 2: printResult(s, i - 1, j); break; case 3: printResult(s, i, j - 1); break; } } /////////////////////Ginoo.ir //////////// int main(){ string inputStr, revStr; int i, n; cin >> n; while (n--){ cin >> inputStr; revStr = ""; for (i = 0; i < inputStr.length(); i++) revStr = inputStr[i] + revStr; cout << LCS(inputStr, revStr, inputStr.length()) << endl; printResult(inputStr, inputStr.length(), inputStr.length()); cout << endl << endl; } getch(); return 0; }