string_utils.hpp

Go to the documentation of this file.

#ifndef STRING_UTILS_H
#define STRING_UTILS_H
 
#include <functional>
#include <vector>
#include <optional>
#include <queue>
#include <cassert>
#include <unordered_map>
#include <sstream>
 
namespace hsc_snippets {
    static std::vector<int> kmpSearch(const std::string &pat, const std::string &txt) {
        const int M = static_cast<int>(pat.size());
        const int N = static_cast<int>(txt.size());
 
        // Longest Prefix Suffix (lps) array
        std::vector<int> lps(M);
        std::vector<int> result;
 
        // Preprocess the pattern
        int len = 0;
        lps[0] = 0; // lps[0] is always 0
        int i = 1;
        while (i < M) {
            if (pat[i] == pat[len]) {
                len++;
                lps[i] = len;
                i++;
            } else {
                if (len != 0) {
                    len = lps[len - 1];
                } else {
                    lps[i] = 0;
                    i++;
                }
            }
        }
 
        // Search the pattern in txt
        i = 0; // index for txt[]
        int j = 0; // index for pat[]
        while (i < N) {
            if (pat[j] == txt[i]) {
                j++;
                i++;
            }
 
            if (j == M) {
                result.push_back(i - j);
                j = lps[j - 1];
            } else if (i < N && pat[j] != txt[i]) {
                if (j != 0) {
                    j = lps[j - 1];
                } else {
                    i = i + 1;
                }
            }
        }
 
        return result;
    }
 
    static bool isPalindrome(const std::string &s) {
        assert(!s.empty());
        const int n = static_cast<int>(s.size());
        for (int i = 0; i < n / 2; i++) {
            if (s[i] != s[n - 1 - i]) {
                return false;
            }
        }
        return true;
    }
 
    template<std::integral T>
    std::string to_string(const std::vector<T> &vec) {
        std::stringstream ss;
        ss << "[";
        for (size_t i = 0; i < vec.size(); ++i) {
            ss << vec[i];
            if (i < vec.size() - 1) {
                // Check if it's not the last element
                ss << ", ";
            }
        }
        ss << "]";
        return ss.str();
    }
 
    template<std::integral T>
    std::string to_string(std::pair<T, T> p) {
        std::stringstream ss;
        ss << "{";
        ss << p.first;
        ss << ", ";
        ss << p.second;
        ss << "}";
        return ss.str();
    }
 
    template<std::integral T>
    std::string to_string(const std::vector<std::pair<T, T> > &vec) {
        std::stringstream ss;
        ss << "[";
        for (size_t i = 0; i < vec.size(); ++i) {
            ss << to_string(vec[i]);
            if (i < vec.size() - 1) {
                // Check if it's not the last element
                ss << ", ";
            }
        }
        ss << "]";
        return ss.str();
    }
 
    static std::string to_string(const std::vector<std::string> &vec) {
        std::stringstream ss;
        ss << "[";
        for (size_t i = 0; i < vec.size(); ++i) {
            ss << vec[i];
            if (i < vec.size() - 1) {
                // Check if it's not the last element
                ss << ", ";
            }
        }
        ss << "]";
        return ss.str();
    }
 
    template<std::integral T>
    std::string to_string(const std::vector<std::vector<T> > &vec) {
        std::stringstream ss;
        ss << "[";
        for (size_t i = 0; i < vec.size(); ++i) {
            ss << to_string(vec[i]);
            if (i < vec.size() - 1) {
                // Check if it's not the last element
                ss << ", ";
            }
        }
        ss << "]";
        return ss.str();
    }
 
    static std::vector<std::string> string_split(const std::string &s, char delimiter) {
        std::vector<std::string> tokens;
        std::string token;
        std::istringstream tokenStream(s);
        while (std::getline(tokenStream, token, delimiter)) {
            tokens.push_back(token);
        }
        return tokens;
    }
 
    static std::string string_repeat(const std::string &s, size_t n) {
        if (n == 0) return "";
        if (n == 1) return s;
        if (s.empty()) return "";
 
        std::string result;
        result.reserve(n * s.size());
 
        size_t current_length = s.size();
        while (result.size() + current_length <= n * s.size()) {
            result += s;
        }
 
        // Append the remaining part to reach exactly n * s.size()
        result += result.substr(0, (n * s.size()) - result.size());
 
        return result;
    }
 
    static std::string string_repeat(char c, size_t n) {
        if (n == 0) return "";
        std::string result(n, c);
        return result;
    }
 
    static std::string string_join(const std::vector<std::string> &strings, const std::string &delimiter) {
        if (strings.empty()) return "";
 
        std::ostringstream result;
        auto iter = strings.begin();
        result << *iter++; // Add the first element without the delimiter
 
        while (iter != strings.end()) {
            result << delimiter << *iter++;
        }
 
        return result.str();
    }
}
 
#endif // STRING_UTILS_H