Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- vector<vector<int>> dp;
- string s;
- int solve(int l, int r){
- string a = "";
- string b = "";
- for(int i = l; i < (l + r + 1) / 2; ++i){
- a += s[i];
- string c;
- c.push_back(s[r - i + l]);
- b = c + b;
- if(a == b){
- return(a.size());
- }
- }
- return 0;
- }
- int f(int l, int r){
- if(l == r){
- return 1;
- }
- if(dp[l][r] != 0){
- return(dp[l][r]);
- }
- int x = solve(l, r);
- if(x == 0){
- dp[l][r] = r - l + 1;
- }
- else{
- dp[l][r] = max(f(l + x, r), f(l, r - x));
- }
- return(dp[l][r]);
- }
- int main() {
- cin >> s;
- dp.resize(s.size(), vector<int>(s.size()));
- f(0, s.size() - 1);
- cout << dp[0][s.size() - 1] << "\n";
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement