• Source 
    1. #include<iostream>
    2. #include<vector>
    3. #include<string>
    4.  
    5. using namespace std;
    6.  
    7. ///Function to print the array
    8. void printArray(vector<int>& v)
    9. {
    10.     for(int i=0;i<v.size();++i)
    11.     {
    12.         cout<<v[i];
    13.     }
    14.     cout<<endl;
    15. }
    16.  
    17. ///Function to convert string to number array
    18. void convertToIntArray(vector<int>& v, string& s)
    19. {
    20.     for(int i=0;i<s.size();++i)
    21.     {
    22.         int no = s[i] - 48;
    23.         v.push_back(no);
    24.     }
    25. }
    26.  
    27. ///Funtion to check if all 9s
    28. bool isAll9(vector<int>& v)
    29. {
    30.     for(int i=0;i<v.size();++i)
    31.     {
    32.         if(v[i]!=9)
    33.             return false;
    34.     }
    35.     return true;
    36. }
    37.  
    38. ///Funtion for type 2 and 3
    39. void genrateNextPalindromeUtil(vector<int>& v)
    40. {
    41.     int n = v.size();
    42.     int mid = n/2;
    43.  
    44.     ///A bool variable to check if copy of left side to right side is sufficient or not
    45.     bool leftsmaller = false;
    46.  
    47.     int i = mid - 1;
    48.     int j = (n % 2)? mid + 1 : mid;
    49.  
    50.     while(i>=0 && v[i] == v[j])
    51.         i--,j++;
    52.  
    53.     if(i < 0 || v[i] < v[j])
    54.         leftsmaller = true;
    55.  
    56.     ///Copy the mirror of left to right
    57.     while(i>=0){
    58.         v[j] = v[i];
    59.         ++j;
    60.         --i;
    61.     }
    62.  
    63.     if(leftsmaller)
    64.     {
    65.         int carry = 1;
    66.         i = mid - 1;
    67.         if(n%2 == 1)
    68.         {
    69.             v[mid] += carry;
    70.             carry = v[mid]/10;
    71.             v[mid] = v[mid]%10;
    72.             j = mid + 1;
    73.         }
    74.         else
    75.             j = mid;
    76.  
    77.         while(i>=0)
    78.         {
    79.             v[i] += carry;
    80.             carry = v[i] /10;
    81.             v[i] = v[i] % 10;
    82.             v[j++] = v[i--];
    83.         }
    84.     }
    85. }
    86.  
    87. ///Funtion to print next palindrome
    88. void generateNextPalindrome(vector<int>& v)
    89. {
    90.     int n = v.size();
    91.     ///Input type 1
    92.     if(isAll9(v))
    93.     {
    94.         cout<<"1";
    95.         for(int i=0;i<n;++i)
    96.         {
    97.             cout<<"0";
    98.         }
    99.         cout<<"1"<<endl;
    100.     }
    101.     else{
    102.  
    103.         genrateNextPalindromeUtil(v);
    104.         printArray(v);
    105.  
    106.  
    107.     }
    108.  
    109. }
    110.  
    111.  
    112.  
    113. int main()
    114. {
    115.     int t;
    116.     cin>>t;
    117.     vector<int> v;
    118.  
    119.     while(t--){
    120.  
    121.         string s;
    122.         cin>>s;
    123.  
    124.         convertToIntArray(v,s);
    125.         generateNextPalindrome(v);
    126.         v.clear();
    127.     }
    128.     return 0;
    129. }
    130.