C++: Tìm tiền tố chung dài nhất (Longest Common Prefix) của tập chuỗi

Cho một mảng các chuỗi, tìm chuỗi tiền tố (prefix) dài nhất xuất hiện ở đầu mọi chuỗi trong mảng.

Ý tưởng

• Lấy chuỗi đầu tiên làm tiền tố ứng viên ban đầu.
• Duyệt qua các chuỗi còn lại, thu hẹp tiền tố bằng cách so sánh ký tự từng cặp.
• Khi tiền tố rỗng → dừng sớm.

Hàm so sánh tiền tố của 2 chuỗi

string commonPrefix(const string& s1, const string& s2) {
    int n = min(s1.size(), s2.size());
    int i = 0;
    while (i < n && s1[i] == s2[i]) ++i;
    return s1.substr(0, i);
}

Hàm chính

string longestCommonPrefix(vector& strs) {
    if (strs.empty()) return "";
    string prefix = strs[0];
    for (size_t i = 1; i < strs.size(); ++i) {
        prefix = commonPrefix(prefix, strs[i]);
        if (prefix.empty()) break; // Tối ưu: dừng sớm
    }
    return prefix;
}

Chương trình hoàn chỉnh

#include <bits/stdc++.h>
using namespace std;

string commonPrefix(const string& s1, const string& s2) {
    int n = min(s1.size(), s2.size());
    int i = 0;
    while (i < n && s1[i] == s2[i]) ++i;
    return s1.substr(0, i);
}

string longestCommonPrefix(vector& strs) {
    if (strs.empty()) return "";
    string prefix = strs[0];
    for (size_t i = 1; i < strs.size(); ++i) {
        prefix = commonPrefix(prefix, strs[i]);
        if (prefix.empty()) break;
    }
    return prefix;
}

int main() {
    vector arr = {"Tutorialspoint", "Tutor", "Tutorials"};
    string res = longestCommonPrefix(arr);
    if (!res.empty())
        cout << "Tien to chung dai nhat: " << res << '\n';
    else
        cout << "Khong co tien to chung\n";
    return 0;
}

Kết quả

Tien to chung dai nhat: Tutor

Phân tích độ phức tạp

• Thời gian: O(S) với S là tổng độ dài tất cả chuỗi. Tốt nhất O(n * minLen).
• Không gian: O(1) bổ sung (chỉ dùng biến prefix).

Các phương pháp khác

Phương pháp duyệt ngang (horizontal scan) như ví dụ trên là đơn giản, dễ hiểu và đủ hiệu quả cho hầu hết bài toán thực tế.