Cerinta completa

You have two strings, and . Find a string, , such that:

  • can be expressed as where is a non-empty substring of and is a non-empty substring of .
  • is a palindromic string.
  • The length of is as long as possible.

For each of the pairs of strings ( and ) received as input, find and print string on a new line. If you’re able to form more than one valid string , print whichever one comes first alphabetically. If there is no valid answer, print instead.

Input Format

The first line contains a single integer, , denoting the number of queries. The subsequent lines describe each query over two lines:

  1. The first line contains a single string denoting .
  2. The second line contains a single string denoting .

Constraints

  • and contain only lowercase English letters.
  • Sum of |a| over all queries does not exceed
  • Sum of |b| over all queries does not exceed

Output Format

For each pair of strings ( and ), find some satisfying the conditions above and print it on a new line. If there is no such string, print instead.

Sample Input

3
bac
bac
abc
def
jdfh
fds

Sample Output

aba
-1
dfhfd

Explanation

We perform the following three queries:

  1. Concatenate with to create .
  2. We’re given and ; because both strings are composed of unique characters, we cannot use them to form a palindromic string. Thus, we print .
  3. Concatenate with to create . Note that we chose these particular substrings because the length of string must be maximal.

Limbajul de programare folosit: cpp20

Cod:

#include <bits/stdc++.h>

using namespace std;

string ltrim(const string &);
string rtrim(const string &);

/*
 * Complete the 'buildPalindrome' function below.
 *
 * The function is expected to return a STRING.
 * The function accepts following parameters:
 *  1. STRING a
 *  2. STRING b
 */

using ull = unsigned long long;

static const ull B1 = 1315423911ULL;
static const ull B2 = 11400714819323198485ULL;

static vector<ull> POW1(1, 1), POW2(1, 1);

static void ensurePow(int n) {
    while ((int)POW1.size() <= n) {
        POW1.push_back(POW1.back() * B1);
        POW2.push_back(POW2.back() * B2);
    }
}

struct Hash2 {
    ull h1 = 0;
    ull h2 = 0;
    bool operator==(const Hash2& o) const {
        return h1 == o.h1 && h2 == o.h2;
    }
};

static Hash2 combineHash(const Hash2& left, int rightLen, const Hash2& right) {
    ensurePow(rightLen);
    return {
        left.h1 * POW1[rightLen] + right.h1,
        left.h2 * POW2[rightLen] + right.h2
    };
}

struct Rolling {
    vector<ull> p1;
    vector<ull> p2;

    Rolling() = default;

    explicit Rolling(const string& s) {
        init(s);
    }

    void init(const string& s) {
        int n = (int)s.size();
        ensurePow(n);
        p1.assign(n + 1, 0);
        p2.assign(n + 1, 0);
        for (int i = 0; i < n; ++i) {
            ull v = (ull)(s[i] - 'a' + 1);
            p1[i + 1] = p1[i] * B1 + v;
            p2[i + 1] = p2[i] * B2 + v;
        }
    }

    Hash2 get(int l, int r) const {
        if (l > r) return {0, 0};
        int len = r - l + 1;
        ensurePow(len);
        return {
            p1[r + 1] - p1[l] * POW1[len],
            p2[r + 1] - p2[l] * POW2[len]
        };
    }
};

struct StrHasher {
    string s;
    string rs;
    Rolling fwd;
    Rolling rev;

    StrHasher() = default;

    explicit StrHasher(const string& str) {
        init(str);
    }

    void init(const string& str) {
        s = str;
        rs.assign(str.rbegin(), str.rend());
        fwd.init(s);
        rev.init(rs);
    }

    int size() const {
        return (int)s.size();
    }

    Hash2 sub(int l, int r) const {
        return fwd.get(l, r);
    }

    // Hash of reverse(s[l..r]).
    Hash2 revSub(int l, int r) const {
        int n = size();
        int rl = n - 1 - r;
        int rr = n - 1 - l;
        return rev.get(rl, rr);
    }
};

struct SAMNode {
    int next[26];
    int link;
    int len;

    SAMNode() : link(-1), len(0) {
        memset(next, -1, sizeof(next));
    }
};

struct SuffixAutomaton {
    vector<SAMNode> st;
    int last;

    void init(int maxLen) {
        st.clear();
        st.reserve(2 * maxLen + 5);
        st.push_back(SAMNode());
        last = 0;
    }

    void extend(char ch) {
        int c = ch - 'a';
        int cur = (int)st.size();
        st.push_back(SAMNode());
        st[cur].len = st[last].len + 1;

        int p = last;
        while (p != -1 && st[p].next[c] == -1) {
            st[p].next[c] = cur;
            p = st[p].link;
        }

        if (p == -1) {
            st[cur].link = 0;
        } else {
            int q = st[p].next[c];
            if (st[p].len + 1 == st[q].len) {
                st[cur].link = q;
            } else {
                int clone = (int)st.size();
                st.push_back(st[q]);
                st[clone].len = st[p].len + 1;
                while (p != -1 && st[p].next[c] == q) {
                    st[p].next[c] = clone;
                    p = st[p].link;
                }
                st[q].link = st[cur].link = clone;
            }
        }
        last = cur;
    }

    vector<int> longestEndingMatches(const string& t) const {
        vector<int> res(t.size(), 0);
        int v = 0;
        int l = 0;

        for (int i = 0; i < (int)t.size(); ++i) {
            int c = t[i] - 'a';

            while (v != 0 && st[v].next[c] == -1) {
                v = st[v].link;
                l = st[v].len;
            }

            if (st[v].next[c] != -1) {
                v = st[v].next[c];
                ++l;
            } else {
                v = 0;
                l = 0;
            }

            res[i] = l;
        }

        return res;
    }
};

static void manacher(const string& s, vector<int>& d1, vector<int>& d2) {
    int n = (int)s.size();
    d1.assign(n, 0);
    int l = 0, r = -1;
    for (int i = 0; i < n; ++i) {
        int k = (i > r) ? 1 : min(d1[l + r - i], r - i + 1);
        while (i - k >= 0 && i + k < n && s[i - k] == s[i + k]) ++k;
        d1[i] = k;
        if (i + k - 1 > r) {
            l = i - k + 1;
            r = i + k - 1;
        }
    }

    d2.assign(n, 0);
    l = 0;
    r = -1;
    for (int i = 0; i < n; ++i) {
        int k = (i > r) ? 0 : min(d2[l + r - i + 1], r - i + 1);
        while (i - k - 1 >= 0 && i + k < n && s[i - k - 1] == s[i + k]) ++k;
        d2[i] = k;
        if (i + k - 1 > r) {
            l = i - k;
            r = i + k - 1;
        }
    }
}

static vector<int> longestPalStart(const string& s) {
    int n = (int)s.size();
    if (n == 0) return {};

    vector<int> d1, d2;
    manacher(s, d1, d2);

    vector<int> best(n, 1);

    // odd palindromes
    vector<vector<pair<int, int>>> add(n);
    for (int c = 0; c < n; ++c) {
        int rad = d1[c];
        int L = c - rad + 1;
        int R = c;
        int key = 2 * c + 1;
        add[L].push_back({key, R});
    }

    priority_queue<pair<int, int>> pq;
    for (int i = 0; i < n; ++i) {
        for (auto &ev : add[i]) pq.push(ev);
        while (!pq.empty() && pq.top().second < i) pq.pop();
        if (!pq.empty()) best[i] = max(best[i], pq.top().first - 2 * i);
    }

    // even palindromes
    add.assign(n, {});
    for (int c = 0; c < n; ++c) {
        int rad = d2[c];
        if (rad == 0) continue;
        int L = c - rad;
        int R = c - 1;
        int key = 2 * c;
        add[L].push_back({key, R});
    }

    while (!pq.empty()) pq.pop();
    for (int i = 0; i < n; ++i) {
        for (auto &ev : add[i]) pq.push(ev);
        while (!pq.empty() && pq.top().second < i) pq.pop();
        if (!pq.empty()) best[i] = max(best[i], pq.top().first - 2 * i);
    }

    return best;
}

struct Candidate {
    const StrHasher* hs = nullptr;
    int end = -1;
    int k = 0;
    int mid = 0;
    int total = 0;
    bool valid = false;
};

static Hash2 prefixHash(const Candidate& c, int len) {
    if (len <= 0) return {0, 0};

    int start = c.end - c.k + 1;
    int firstPart = c.k + c.mid;

    if (len <= firstPart) {
        return c.hs->sub(start, start + len - 1);
    }

    Hash2 left = c.hs->sub(start, start + firstPart - 1);
    int t = len - firstPart;
    Hash2 right = c.hs->revSub(c.end - t + 1, c.end);
    return combineHash(left, t, right);
}

static char charAt(const Candidate& c, int pos) {
    int start = c.end - c.k + 1;
    int firstPart = c.k + c.mid;

    if (pos < firstPart) {
        return c.hs->s[start + pos];
    }

    int t = pos - firstPart;
    return c.hs->s[c.end - t];
}

static bool lexLess(const Candidate& a, const Candidate& b) {
    if (!b.valid) return a.valid;
    if (!a.valid) return false;

    int n = a.total;
    int lo = 0, hi = n;
    while (lo < hi) {
        int mid = (lo + hi + 1) >> 1;
        if (prefixHash(a, mid) == prefixHash(b, mid)) lo = mid;
        else hi = mid - 1;
    }

    if (lo == n) return false;
    return charAt(a, lo) < charAt(b, lo);
}

static string materialize(const Candidate& c) {
    int start = c.end - c.k + 1;
    string res;
    res.reserve(c.total);

    res += c.hs->s.substr(start, c.k + c.mid);
    for (int i = c.k - 1; i >= 0; --i) {
        res.push_back(c.hs->s[start + i]);
    }

    return res;
}

string buildPalindrome(string a, string b) {
    string rb(b.rbegin(), b.rend());

    vector<int> palA = longestPalStart(a);
    vector<int> palRB = longestPalStart(rb);

    SuffixAutomaton samRB;
    samRB.init((int)rb.size());
    for (char ch : rb) samRB.extend(ch);
    vector<int> matchA = samRB.longestEndingMatches(a);

    SuffixAutomaton samA;
    samA.init((int)a.size());
    for (char ch : a) samA.extend(ch);
    vector<int> matchRB = samA.longestEndingMatches(rb);

    StrHasher hA(a), hRB(rb);

    Candidate best;

    int n = (int)a.size();
    for (int i = 0; i < n; ++i) {
        int k = matchA[i];
        if (k <= 0) continue;
        int mid = (i + 1 < n) ? palA[i + 1] : 0;

        Candidate cur;
        cur.hs = &hA;
        cur.end = i;
        cur.k = k;
        cur.mid = mid;
        cur.total = 2 * k + mid;
        cur.valid = true;

        if (!best.valid || cur.total > best.total || (cur.total == best.total && lexLess(cur, best))) {
            best = cur;
        }
    }

    int m = (int)rb.size();
    for (int j = 0; j < m; ++j) {
        int k = matchRB[j];
        if (k <= 0) continue;
        int mid = (j + 1 < m) ? palRB[j + 1] : 0;

        Candidate cur;
        cur.hs = &hRB;
        cur.end = j;
        cur.k = k;
        cur.mid = mid;
        cur.total = 2 * k + mid;
        cur.valid = true;

        if (!best.valid || cur.total > best.total || (cur.total == best.total && lexLess(cur, best))) {
            best = cur;
        }
    }

    if (!best.valid) return "-1";
    return materialize(best);
}

int main()
{
    ofstream fout(getenv("OUTPUT_PATH"));

    string q_temp;
    getline(cin, q_temp);

    int q = stoi(ltrim(rtrim(q_temp)));

    for (int q_itr = 0; q_itr < q; q_itr++) {
        string a;
        getline(cin, a);

        string b;
        getline(cin, b);

        string result = buildPalindrome(a, b);

        fout << result << endl;
    }

    fout.close();

    return 0;
}

string ltrim(const string &str) {
    string s(str);

    s.erase(
        s.begin(),
        find_if(s.begin(), s.end(), not1(ptr_fun<int, int>(isspace)))
    );

    return s;
}

string rtrim(const string &str) {
    string s(str);

    s.erase(
        find_if(s.rbegin(), s.rend(), not1(ptr_fun<int, int>(isspace))).base(),
        s.end()
    );

    return s;
}

Scor obtinut: 1.0

Submission ID: 464635902

Link challenge: https://www.hackerrank.com/challenges/challenging-palindromes/problem

Build a Palindrome