Palindromic decompositions

palin.cxx

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

struct range {
    const char* start;
    const char* end;
};

/// Check if a range is palindromic.
bool is_palindrome(range r) {
    if (r.start == r.end) return true;

    auto front = r.start;
    auto back = r.end - 1;
    while (front < back) {
        if (*front++ != *back--) return false;
    }
    return true;
}

void print_palindromic_decompositions(const std::string& s) {
    if (s.empty()) return;

    auto start = s.data();
    auto end = s.data() + s.size();

    // A (partial) decomposition of s into palindromic ranges, ie.
    //   1. d[0].start == start
    //   2. d[i].end == d[i+1].start
    //   3. is_palindrome(d[i])
    // If in addition
    //   4. d.back().end == end
    // then we say that it is a full decomposition (these are what we
    // need to print); otherwise we say it is a partial decomposition.
    std::vector<range> d;
    d.reserve(s.size());
    // When d is a partial decomposition, fill it with length 1 ranges
    // until it is a full decomposition.
    auto fill_with_singletons = [&]() {
        if (d.empty()) {
            d.push_back(range { start, start + 1 });
        }
        while (d.back().end != end) {
            auto last = d.back().end;
            d.push_back(range { last, last + 1 });
        }
    };
    // Print the current decomposition.
    auto print_decomposition = [&]() {
        for (auto r : d) {
            std::cout << "[";
            for (auto p = r.start; p != r.end; ++p) std::cout << *p;
            std::cout << "]";
        }
        std::cout << "\n";
    };

    fill_with_singletons();

    while (!d.empty()) {
        auto& back = d.back();
        if (back.end == end) {
            print_decomposition();
            d.pop_back();
            continue;
        }
        for(;;) {
            ++back.end;
            if (is_palindrome(back)) {
                fill_with_singletons();
                break;
            }
            if (back.end == end) {
                d.pop_back();
                break;
            }
        }
    }
}

int main() {
    print_palindromic_decompositions("11123433223");
}