Question

How to find the longest common prefix of all the words in a string with C++

Answer 1

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

// Extract lowercase alphabetic words
std::vector<std::string> extract_words(const std::string& s) {
    std::vector<std::string> words;
    std::string current;

    for (char c : s) {
        if (std::isalpha(static_cast<unsigned char>(c))) {
            current.push_back(std::tolower(c));
        } else if (!current.empty()) {
            words.push_back(current);
            current.clear();
        }
    }
    if (!current.empty())
        words.push_back(current);

    return words;
}

// Longest common prefix of two strings
std::string lcp_two(const std::string& a, const std::string& b) {
    size_t i = 0;
    while (i < a.size() && i < b.size() && a[i] == b[i])
        ++i;
    return a.substr(0, i);
}

// Longest common prefix of ALL words (like your Python version)
std::string longest_common_prefix(const std::string& s) {
    auto words = extract_words(s);
    if (words.empty())
        return "";

    // Sort words so LCP is between first and last
    std::sort(words.begin(), words.end());

    return lcp_two(words.front(), words.back());
}

int main() {
    std::string s1 = "The lowly inhabitants of the lowland were surprised to see the lower branches.";
    std::string s2 = "unclear, uncertain, unexpected";

    std::cout << "LCP: '" << longest_common_prefix(s1) << "'\n"; // ""
    std::cout << "LCP: '" << longest_common_prefix(s2) << "'\n"; // "un"
}



/*
run:

LCP: ''
LCP: 'un'

*/

 

70+ SQL courses for beginners and professionals

Answer 2

#include <iostream>
#include <regex>
#include <string>
#include <vector>

std::vector<std::string> splitWordsRegex(const std::string& input) {
    std::regex re("\\W+");  // same meaning as Java: split on non‑word chars
    std::sregex_token_iterator it(input.begin(), input.end(), re, -1);
    std::sregex_token_iterator end;

    std::vector<std::string> words;
    for (; it != end; ++it) {
        if (!it->str().empty()) {
            std::string w = *it;
            std::transform(w.begin(), w.end(), w.begin(),
                           [](unsigned char c){ return std::tolower(c); });
            words.push_back(w);
        }
    }
    return words;
}

std::string longestCommonPrefix(const std::string& input) {
    auto words = splitWordsRegex(input);
    if (words.empty()) return "";

    std::string prefix = words[0];

    for (size_t i = 1; i < words.size(); ++i) {
        while (words[i].rfind(prefix, 0) != 0) { // prefix not at start
            prefix.pop_back();
            if (prefix.empty()) return "";
        }
    }
    return prefix;
}

int main() {
    std::string s1 = "The lowly inhabitants of the lowland were surprised to see the lower branches.";
    std::cout << "LCP: '" << longestCommonPrefix(s1) << "'\n";

    std::string s2 = "unclear, uncertain, unexpected";
    std::cout << "LCP: '" << longestCommonPrefix(s2) << "'\n";
}



/*
run:

LCP: ''
LCP: 'un'

*/

 

70+ SQL courses for beginners and professionals

Answer 3

#include <iostream>
#include <string>
#include <vector>

std::vector<std::string> splitWords(const std::string& s) {
    std::vector<std::string> out;
    std::string cur;

    for (char c : s) {
        if (std::isalnum(c) || c == '_') {
            cur.push_back(std::tolower(c));
        } else if (!cur.empty()) {
            out.push_back(cur);
            cur.clear();
        }
    }
    if (!cur.empty()) out.push_back(cur);
    
    return out;
}

std::string longestCommonPrefix(const std::string& input) {
    auto words = splitWords(input);
    if (words.empty()) return "";

    std::string prefix = words[0];

    for (const auto& w : words) {
        auto mismatchPair = std::mismatch(prefix.begin(), prefix.end(),
                                          w.begin(), w.end());
        prefix.erase(mismatchPair.first, prefix.end());
        if (prefix.empty()) return "";
    }
    
    return prefix;
}

int main() {
    std::cout << longestCommonPrefix("The lowly inhabitants of the lowland were surprised to see the lower branches.") << "\n";
    std::cout << longestCommonPrefix("unclear, uncertain, unexpected") << "\n";
}




/*
run:


un

*/

 

70+ SQL courses for beginners and professionals

Answer 4

#include <iostream>
#include <sstream>
#include <vector>

std::string longestCommonPrefix(const std::string& input) {
    if (input.empty()) return "";

    // Convert to lowercase
    std::string lower;
    lower.reserve(input.size());
    for (char c : input) lower.push_back(std::tolower(c));

    // Split by non‑word characters
    std::vector<std::string> words;
    std::string word;
    for (char c : lower) {
        if (std::isalnum(c) || c == '_') {
            word.push_back(c);
        } else if (!word.empty()) {
            words.push_back(word);
            word.clear();
        }
    }
    if (!word.empty()) words.push_back(word);

    if (words.empty()) return "";

    // Start with the first word as prefix
    std::string prefix = words[0];

    for (size_t i = 1; i < words.size(); ++i) {
        while (words[i].rfind(prefix, 0) != 0) { // prefix not at start
            prefix.pop_back();
            if (prefix.empty()) return "";
        }
    }
    return prefix;
}

int main() {
    std::string s1 = "The lowly inhabitants of the lowland were surprised to see the lower branches.";
    std::cout << "LCP: '" << longestCommonPrefix(s1) << "'\n";

    std::string s2 = "unclear, uncertain, unexpected";
    std::cout << "LCP: '" << longestCommonPrefix(s2) << "'\n";
}




/*
run:

LCP: ''
LCP: 'un'

*/

 

70+ SQL courses for beginners and professionals