Grupe X - 6.6.4 / pag 173

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int M;
    cin >> M;
    map < string , bool > mp;
    for(int i = 0; i < M; ++i) {
        string s;
        cin >> s;
        mp[s] = true;
    }
    int N;
    cin >> N;
    string s;
    cin >> s;
    vector < int > dp(N + 1, INF), poz(N + 1);
    dp[0] = 0;
    poz[0] = -1;
    for(int i = 1; i <= N; ++i)
        for(int j = 0; j < i; ++j) {
            string t;
            for(int k = j; k < i; ++k)
                t.push_back(s[k]);
            if(mp[t] && dp[i] > dp[j] + 1) {
                dp[i] = dp[j] + 1;
                poz[i] = j;
            }
        }
    if(dp[N] == INF) {
        cout << -1;
        return 0;
    }
    cout << dp[N] << '\n';
    int i = poz[N], last = N;
    vector < string > sol;
    while(i != -1) {
        string aux;
        for(int j = i; j < last; ++j)
            aux.push_back(s[j]);
        sol.push_back(aux);
        last = i;
        i = poz[i];
    }
    reverse(sol.begin(), sol.end());
    for(string x : sol)
        cout << x << '\n';
}