Advertisement
Guest User

Runtime Error

a guest
Apr 6th, 2020
126
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.91 KB | None | 0 0
  1. tuple<int, int> find_left_right(const string &s, int i, int j, char a)
  2. {
  3.     int left = -1;
  4.     int right = -1;
  5.     for (int p = i; p <= j; p++)
  6.     {
  7.         if (s[p] == a)
  8.         {
  9.             if (left == -1) left = p;
  10.             right = p;
  11.         }
  12.     }
  13.    
  14.     return make_tuple(left, right);
  15. }
  16.  
  17. unsigned long long Cast(unsigned long long value)
  18. {
  19.     if (value > static_cast<unsigned long long>(pow(10, 19)))
  20.         value %= static_cast<unsigned long long>(pow(10, 19));
  21.     return value;
  22. }
  23.  
  24. class Solution {
  25. public:
  26.     int countPalindromicSubsequences(string S) {
  27.         vector<vector<unsigned long long>> dp(S.length(), vector<unsigned long long>(S.length(), 0));
  28.         for (int i = 0; i < S.length(); i++)
  29.             dp[i][i] = 1;
  30.        
  31.         for (int step = 1; step < S.length(); step++)
  32.         {
  33.             for (int i = 0; i < S.length() - step; i++)
  34.             {
  35.                 int j = i + step;
  36.                 if (j >= S.length()) break;
  37.                
  38.                 if (S[i] != S[j])
  39.                 {
  40.                     dp[i][j] = Cast(dp[i + 1][j] + dp[i][j - 1] - dp[i + 1][j - 1]);
  41.                 }
  42.                 else
  43.                 {
  44.                     int l, r;
  45.                     tie(l, r) = find_left_right(S, i + 1, j - 1, S[i]);
  46.                    
  47.                     if (l == -1)
  48.                     {
  49.                         dp[i][j] = Cast(dp[i + 1][j - 1] * 2) + 2;
  50.                     }
  51.                     else if (l == r)
  52.                     {
  53.                         dp[i][j] = Cast(dp[i + 1][j - 1] * 2) + 1;
  54.                     }
  55.                     else
  56.                     {
  57.                         dp[i][j] = Cast(Cast(dp[i + 1][j - 1] * 2)  - dp[l + 1][r - 1]);
  58.                     }
  59.                 }
  60.             }
  61.         }
  62.        
  63.         return dp[0].back() % static_cast<int>(pow(10, 9) + 7);
  64.     }
  65.    
  66.    
  67. };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement