SHARE
TWEET

Untitled

a guest Oct 13th, 2019 77 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <fstream>
  3. #include <string>
  4.  
  5. using namespace std;
  6.  
  7. int** new_matrix(int height, int width)
  8. {
  9.     int** mx = new int* [height];
  10.     for (int i = 0; i < height; i++)
  11.     {
  12.         mx[i] = new int[width];
  13.     }
  14.     return mx;
  15. }
  16.  
  17. void reverseStr(string& str)
  18. {
  19.     int n = str.length();
  20.     for (int i = 0; i < n / 2; i++)
  21.     {
  22.         swap(str[i], str[n - i - 1]);
  23.     }
  24. }
  25.  
  26. int main()
  27. {
  28.     ifstream IN;
  29.     ofstream OUT;
  30.     IN.open("input.txt");
  31.  
  32.     string str = "";
  33.     getline(IN, str);
  34.  
  35.     IN.close();
  36.  
  37.     int n = str.length();
  38.  
  39.     int** matrix = new_matrix(n, n);
  40.  
  41.     for (int i = 0; i < n; i++)
  42.     {
  43.         matrix[i][i] = 1;
  44.     }
  45.  
  46.     int s_j = 1;
  47.     int j = 1;
  48.     int i = 0;
  49.     for (int k = 0; k < n; k++)
  50.     {
  51.         for (i; i < n; i++)
  52.         {
  53.             if (i + 1 == j)
  54.             {
  55.                 if (str[i] != str[j])
  56.                 {
  57.                     matrix[i][j] = 1;
  58.                 }
  59.                 else
  60.                 {
  61.                     matrix[i][j] = 2;
  62.                 }
  63.             }
  64.  
  65.             else if (i == j)
  66.             {
  67.                 matrix[i][j] = 1;
  68.             }
  69.  
  70.             else if (j > i)
  71.             {
  72.                 if (str[i] != str[j])
  73.                 {
  74.                     if (matrix[i][j - 1] > matrix[i + 1][j])
  75.                     {
  76.                         matrix[i][j] = matrix[i][j - 1];
  77.                     }
  78.                     else
  79.                     {
  80.                         matrix[i][j] = matrix[i + 1][j];
  81.                     }
  82.                 }
  83.                 else
  84.                 {
  85.                     matrix[i][j] = matrix[i + 1][j - 1] + 2;
  86.                 }
  87.             }
  88.             if (j < n - 1)
  89.             {
  90.                 j += 1;
  91.             }
  92.         }
  93.         i = 0;
  94.         if (j < n)
  95.         {
  96.             j = s_j + 1;
  97.             s_j = j;
  98.         }
  99.     }
  100.  
  101.     int length = matrix[0][n - 1];
  102.     i = 0;
  103.     j = n - 1;
  104.     string half_result_string = "";
  105.  
  106.     while (j >= i)
  107.     {
  108.         if (str[i] == str[j])
  109.         {
  110.             half_result_string += str[i];
  111.             i += 1;
  112.             j -= 1;
  113.         }
  114.         else
  115.         {
  116.             if (matrix[i][j - 1] > matrix[i + 1][j])
  117.             {
  118.                 j -= 1;
  119.             }
  120.             else
  121.             {
  122.                 i += 1;
  123.             }
  124.         }
  125.     }
  126.  
  127.     string buffer = "";
  128.     string final_string = "";
  129.     if (length % 2 != 0)
  130.     {
  131.         buffer = half_result_string[length / 2];
  132.         half_result_string = half_result_string.erase(half_result_string.length() - 1, 1);
  133.         final_string += half_result_string;
  134.         final_string += buffer;
  135.         reverseStr(half_result_string);
  136.         final_string += half_result_string;
  137.     }
  138.     else
  139.     {
  140.         final_string += half_result_string;
  141.         reverseStr(half_result_string);
  142.         final_string += half_result_string;
  143.     }
  144.  
  145.     OUT.open("output.txt");
  146.  
  147.     OUT << length << "\n";
  148.     for (int i = 0; i < length; i++)
  149.     {
  150.         OUT << final_string[i];
  151.     }
  152.  
  153.     OUT.close();
  154. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top