Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- // #pragma comment(linker, "/stack:200000000")
- // #pragma GCC optimize("Ofast")
- // #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
- // - - - - - - Data Types - - - - - - //
- typedef long int LI;
- typedef long long LL;
- // - - - - - - Vectors - - - - - - //
- typedef vector<int> VI;
- typedef vector<LL> VLL;
- typedef vector<string> VS;
- typedef vector<double> VD;
- typedef vector<VI> VVI;
- #define scanVI(v, n) for(int i=0; i<n; i++){ int x; cin >> x; v.PB(x); }
- #define scanVLLI(v, n) for(int i=0; i<n; i++){ LLI x; cin >> x; v.PB(x); }
- #define scanVS(v, n) for(int i=0; i<n; i++){ string x; cin >> x; v.PB(x); }
- #define scanVD(v, n) for(int i=0; i<n; i++){ double x; cin >> x; v.PB(x); }
- // - - - - - - Maps - - - - - - //
- typedef map<int, int> MII;
- typedef map<int, string> MIS;
- typedef map<int, char> MIC;
- typedef map<string, int> MSI;
- typedef map<char, int> MCI;
- typedef map<int, VI> MIVI;
- // - - - - - - Pairs - - - - - - //
- typedef pair<int, int> PII;
- typedef pair<string, string> PSS;
- typedef pair<char, char> PCC;
- typedef pair<int, string> PIS;
- typedef pair<int, char> PIC;
- typedef pair<string, char> PSC;
- // - - - - - - Sets - - - - - - //
- typedef set<int> SI;
- typedef set<LL> SLL;
- typedef set<string> SS;
- typedef set<char> SC;
- // - - - - - - - - - - - - - - - - - - //
- #define PF printf
- #define SF scanf
- #define PB push_back
- #define POP pop_back()
- #define PP prev_permutation
- #define NP next_permutation
- #define MP make_pair
- #define CLRN(a, b) memset(a, b, sizeof(a))
- #define CLR(a) memset(a, 0, sizeof(a))
- #define ALL(a) a.begin(), a.end()
- #define ALLN(a, n) (a, a+n)
- #define BSRCN(a, n, x) binary_search(ALLN(a, n), x)
- #define BSRC binary_search
- #define MAX 10000007
- #define MIN -10000007
- #define inf int(1e6+9)
- #define PI acos(-1)
- #define BR PF("\n")
- #define FastIO ios_base::sync_with_stdio(false)
- #define READ() freopen("input.txt", "r", stdin)
- #define WRITE() freopen("output.txt", "w", stdout)
- #define len(a) a.length()
- #define rsort(a) sort(a.rbegin(), a.rend())
- #define pvec(v) for(auto x: v) cout<<x<<" "
- // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - //
- /*----------------------Graph Moves----------------*/
- int ROW[]={+1,-1,+0,+0};
- int COL[]={+0,+0,+1,-1};
- int X[]={+0,+0,+1,-1,-1,+1,-1,+1}; // Kings Move
- int Y[]={-1,+1,+0,+0,+1,+1,-1,-1}; // Kings Move
- int KX[]={-2, -2, -1, -1, 1, 1, 2, 2}; // Knights Move
- int KY[]={-1, 1, -2, 2, -2, 2, -1, 1}; // Knights Move
- /*------------------------------------------------*/
- void fastscan(int &number)
- {
- bool negative = false;
- int c;
- number = 0;
- c = getchar();
- if (c=='-')
- {
- negative = true;
- c = getchar();
- }
- for (; (c>47 && c<58); c=getchar())
- number = number *10 + c - 48;
- if (negative)
- number *= -1;
- }
- LL GCD(LL a, LL b) { return b == 0 ? a : GCD(b , a % b); }
- int LCM(int a, int b) { return a * (b/GCD(a, b)); }
- bool CMP(int a, int b) { return a>b; }
- // - - - - - - - - - - - - - - - - - - - - - - - - - - - END - - - - - - - - - - - - - - - - - - - - - - - - - //
- int main()
- {
- // FastIO;
- #ifdef HOME
- clock_t Start=clock();
- freopen("in.txt", "r", stdin);
- freopen("out.txt", "w", stdout);
- #endif
- string s;
- cin>>s;
- string rev = s;
- reverse(rev.begin(), rev.end());
- int n = len(s);
- int dp[n+1][n+1];
- for (int i=0; i<=n; i++) {
- for (int j=0; j<=n; j++) {
- if (i==0 or j==0)
- dp[i][j] = 0;
- else if (s[i-1] == rev[j-1])
- dp[i][j] = dp[i-1][j-1] + 1;
- else
- dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
- }
- }
- string lcs = "";
- int i, j, k = dp[n][n], z = k-1;
- int pos[k];
- i = j = n;
- while (i and j) {
- if (s[i-1] == rev[j-1]) {
- lcs += s[i-1];
- pos[z--] = i-1;
- i--; j--;
- }
- else if (dp[i-1][j] > dp[i][j-1])
- i--;
- else
- j--;
- }
- cout<<lcs<<endl;
- // reverse(lcs.begin(), lcs.end());
- // for (int i=0; i<k; i++)
- // cout<<pos[i]<<endl;
- int a = *min_element(pos, pos+k), b = *max_element(pos, pos+k);
- string ans = "";
- bool take = 0;
- j = 0;
- for (i=a; i<=b; i++) {
- if (s[i]==lcs[j]) {
- take = 1;
- k--;
- j++;
- ans += s[i];
- }
- else if (k and take) {
- ans += s[i];
- }
- }
- cout<<ans<<endl;
- END:
- #ifdef HOME
- fprintf(stderr, "\n>>Runtime: %.10fs\n", (double) (clock() - Start) / CLOCKS_PER_SEC);
- #endif
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement