SUPREFIX - Tiền tố và hậu tố

Xem dạng PDF
Gửi bài giải
Điểm: 2,00 (OI)
Giới hạn thời gian: 0.01s
Giới hạn bộ nhớ: 256M
Tác giả:
Hieu Nguyen
Dạng bài
Ngôn ngữ cho phép
C, C#, C++, Go, Java, Pascal, Perl, PHP, Python, Ruby, Rust, Scratch, Swift

Xâu ~a~ được gọi là tiền tố của xâu ~b~ nếu xâu ~a~ trùng với phần đầu của xâu ~b~. Ví dụ pre là tiền tố của prefix.

Xâu ~a~ được gọi là hậu tố của xâu ~b~ nếu xâu ~a~ trùng với phần cuối của xâu ~b~. Ví dụ fix là hậu tố của suffix.

Cho hai xâu ~a~ và ~b~ chỉ gồm các ký tự Latinh thường. Hãy tìm xâu ~c~ có độ dài ngắn nhất sao cho ~a~ là tiền tố của ~c~ và ~b~ là hậu tố của ~c~.

Input

  • Dòng đầu chứa xâu ~a~;
  • Dòng sau chứa xâu ~b~.

Giới hạn:

  • ~1 ≤ |a|,|b| ≤ 10^5~.

Output

  • Xâu ~c~ tìm được.

Sample

Input #1
abca
cab
Output #1
abcab

Problem source: Chuyên Sơn La Online Judge

Bình luận

Hãy đọc nội quy trước khi bình luận.


  • 2
    VuDinhDat  đã bình luận lúc 25, Tháng 11, 2023, 3:51

    include <iostream>

    include <vector>

    include <cstring>

    using namespace std;

    typedef long long ll; typedef pair<int, int> ii;

    define X first

    define Y second

    define pb push_back

    define EL printf("\n")

    define FOR(i, l, r) for (int i = l; i <= r; i++)

    define FOD(i, r, l) for (int i = r; i >= l; i--)

    define fillchar(a, x) memset(a, x, sizeof(a))

    vector<int> Z_Function(const string& s) { int n = s.size(); vector<int> z(n, 0); for (int i = 1, l = 0, r = 0; i < n; i++) { if (i <= r) z[i] = min(z[i - l], r - i + 1); while (i + z[i] < n && s[i + z[i]] == s[z[i]]) ++z[i]; if (i + z[i] - 1 > r) l = i, r = i + z[i] - 1; } return z; }

    int main() { iosbase::syncwith_stdio(false); cin.tie(NULL);

    string a, b;
cin >> a >> b;

string s = b + '#' + a;
vector<int> z = Z_Function(s);

int ans = 0;
for (int i = b.size() + 1; i < s.size(); i++) {
    if (ans < z[i] && i + z[i] == s.size()) ans = z[i];
}

cout << a;
FOR(i, ans, b.size() - 1) cout << b[i];
EL;

return 0;

    }


  • 1
    copy_paste  đã bình luận lúc 7, Tháng 7, 2023, 6:20

    Khóc 0.01s


    • 0
      TQThong2k11  đã bình luận lúc 28, Tháng 11, 2023, 3:15

      xâu mà bạn nên xử lí nhanh lắm