Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- tuple<int, int> find_left_right(const string &s, int i, int j, char a)
- {
- int left = -1;
- int right = -1;
- for (int p = i; p <= j; p++)
- {
- if (s[p] == a)
- {
- if (left == -1) left = p;
- right = p;
- }
- }
- return make_tuple(left, right);
- }
- unsigned long long Cast(unsigned long long value)
- {
- if (value > static_cast<unsigned long long>(pow(10, 19)))
- value %= static_cast<unsigned long long>(pow(10, 19));
- return value;
- }
- class Solution {
- public:
- int countPalindromicSubsequences(string S) {
- vector<vector<unsigned long long>> dp(S.length(), vector<unsigned long long>(S.length(), 0));
- for (int i = 0; i < S.length(); i++)
- dp[i][i] = 1;
- for (int step = 1; step < S.length(); step++)
- {
- for (int i = 0; i < S.length() - step; i++)
- {
- int j = i + step;
- if (j >= S.length()) break;
- if (S[i] != S[j])
- {
- dp[i][j] = Cast(dp[i + 1][j] + dp[i][j - 1] - dp[i + 1][j - 1]);
- }
- else
- {
- int l, r;
- tie(l, r) = find_left_right(S, i + 1, j - 1, S[i]);
- if (l == -1)
- {
- dp[i][j] = Cast(dp[i + 1][j - 1] * 2) + 2;
- }
- else if (l == r)
- {
- dp[i][j] = Cast(dp[i + 1][j - 1] * 2) + 1;
- }
- else
- {
- dp[i][j] = Cast(Cast(dp[i + 1][j - 1] * 2) - dp[l + 1][r - 1]);
- }
- }
- }
- }
- return dp[0].back() % static_cast<int>(pow(10, 9) + 7);
- }
- };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement