C++ Program: หา Longest Common Prefix ของ Array ของ Strings

โจทย์: หา Longest Common Prefix (LCP) ของชุดสตริงหลายตัว คือ Prefix ที่ยาวที่สุดที่ทุกสตริงมีร่วมกัน

Algorithm: Horizontal Scanning

1. ตั้ง Prefix เริ่มต้น = String ตัวแรก
2. Iterate String ตัวถัดไป: หา Common Prefix ระหว่าง Prefix ปัจจุบัน กับ String นี้
3. อัปเดต Prefix ให้สั้นลงตามที่ Match
4. ถ้า Prefix ว่าง → หยุดทันที (ไม่มี Common Prefix)

Complexity

• Time: O(S) โดย S = Sum of all characters ใน Strings ทั้งหมด
• Space: O(1) Extra Space

โค้ด C++

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

// หา Common Prefix ระหว่าง 2 Strings
string commonPrefix(const string& s1, const string& s2) {
    int n = min(s1.length(), s2.length());
    int i = 0;
    while (i < n && s1[i] == s2[i]) i++;
    return s1.substr(0, i);
}

// หา LCP ของ Array
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; // Early exit
    }
    return prefix;
}

// Overload สำหรับ Array แบบเดิม
string longestCommonPrefix(string a[], int n) {
    if (n == 0) return "";
    string pre = a[0];
    for (int i = 1; i < n; i++)
        pre = commonPrefix(pre, a[i]);
    return pre;
}

int main() {
    string arr[] = {"Tutorialspoint", "Tutor", "Tutorials"};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    string result = longestCommonPrefix(arr, n);
    
    if (!result.empty())
        cout << "Longest Common Prefix: " << result << '\n';
    else
        cout << "No common prefix\n";
    
    return 0;
}

ผลลัพธ์

Longest Common Prefix: Tutor

Alternative Algorithms

1. Vertical Scanning (Column by Column)

string lcpVertical(vector& strs) {
    if (strs.empty()) return "";
    for (int col = 0; col < strs[0].size(); col++) {
        char c = strs[0][col];
        for (int row = 1; row < strs.size(); row++) {
            if (col == strs[row].size() || strs[row][col] != c)
                return strs[0].substr(0, col);
        }
    }
    return strs[0];
}

2. Divide & Conquer

string lcpDC(vector& strs, int l, int r) {
    if (l == r) return strs[l];
    int mid = (l + r) / 2;
    string left = lcpDC(strs, l, mid);
    string right = lcpDC(strs, mid+1, r);
    return commonPrefix(left, right);
}

3. Binary Search on Length

bool isCommonPrefix(vector& strs, int len) {
    string prefix = strs[0].substr(0, len);
    for (int i = 1; i < strs.size(); i++)
        if (strs[i].compare(0, len, prefix) != 0)
            return false;
    return true;
}

string lcpBinary(vector& strs) {
    if (strs.empty()) return "";
    int minLen = INT_MAX;
    for (auto& s : strs) minLen = min(minLen, (int)s.length());
    
    int low = 0, high = minLen;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (isCommonPrefix(strs, mid))
            low = mid + 1;
        else
            high = mid - 1;
    }
    return strs[0].substr(0, (low + high) / 2);
}

Trie-based Approach (สำหรับ Query หลายครั้ง)

สร้าง Trie จาก Strings ทั้งหมด LCP = Path จาก Root จนกว่าจะมี Branch > 1 หรือจบคำ

การประยุกต์ใช้

• Autocomplete / Search Suggestions
• File Path Common Directory
• DNA Sequence Analysis
• URL Routing Prefix Matching