Tiền tố và hậu tố - LCOJ: Luyện Code Online Judge

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

Điểm: 2,00 (OI)

Giới hạn thời gian: 0.01s

Giới hạn bộ nhớ: 256M

Tác giả:

Hiếu Nguyễn

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

Please read the guidelines before commenting.

Ý 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