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ả:
Dạng bài
Ngôn ngữ cho phép
C, C#, C++, Go, Java, Pascal, Perl, PHP, PyPy, 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.



  • 0
    khoihahaha  đã bình luận lúc 11, Tháng 6, 2025, 3:04

    Ý tưởng: Dùng thuật toán KMP tìm độ dài k lớn nhất là phần giao giữa tiền tố của b và hậu tố của a. Kết quả bài toán là a cộng với b bỏ k ký tự đầu.

    CODE ĐÃ AC:

    int lps[200001];
    
    void buildLPS(std::string& s)
    {
        int n = s.length();
    
        for (int i = 1; i < n; i++)
        {
            int j = lps[i - 1];
            while (j > 0 && s[i] != s[j]) j = lps[j - 1];
            if (s[i] == s[j]) j++;
            lps[i] = j;
        }
    }
    std::string solve(std::string& a, std::string& b)
    {
        std::string buff = b + '#' + a;
    
        buildLPS(buff);
    
        return a + b.substr(lps[buff.size() - 1]);
    }
    

  • 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