all possible palindrome partitions, C++ (gcc)

all possible palindrome partitions

#include <bits/stdc++.h>

using namespace std;

#define pb push_back

const int N = 100;

vector<string> v[N];

bool isPal[N][N], mark[N];

string s;
int n;

void foo(int l){
    if(l >= n) return;
    if(mark[l]) return;
    mark[l] = 1;
    string cur = "";
    for(int j = l; j < n; j++){
        cur += s[j];
        if(!isPal[l][j]) continue;
        foo(j+1);
        for(auto i : v[j+1])
            v[l].pb(cur + ' ' + i);
    }
}

void print(){
    for(auto i : v[0])
        cout << i << endl;
}

void build(){
    for(int j = 0; j < n; j++){
        isPal[j][j] = 1;
        
        // odd length
        int l = j-1, r = j+1;
        while(l >= 0 && r < n && s[l] == s[r]) isPal[l][r] = 1, l--, r++;
        
        //even length
        l = j, r = j+1;
        while(l >= 0 && r < n && s[l] == s[r]) isPal[l][r] = 1, l--, r++;
    }
}

int main(){
    cin >> s;
    n = s.length();
    memset(mark, 0, sizeof(mark));
    memset(isPal, false, sizeof(isPal));
    
    build();
    v[n].pb("");
    foo(0);
    print();
    return 0;
}


run \| edit \| history \| help	0