PD Dictionar

/*
problema 3 Varianta 2 - Laborator PD
date de intrare in date.in si cod.in - de creat dupa bunul plac

*/


#include<fstream>
#include<iostream>
#include<string>
#include<unordered_set>
using namespace std;
int main()
{
    int n, m, i, j,v[100],pred[100];
    //v[i] - nr minim de cuvinte in care se descompune S[0...i]
    //v[n-1] - scopul meu in viata;
    // v[i>0]= 1 + min{v[j]|j<i, S[j+1...i] is in M}
    //V[0]=1;
    //initial v[i]=i+1;

    string S;
    unordered_set<string> M;
    ifstream fin("date.in");
    string d;
    fin >> m;
    for (i = 0; i < m; i++) { fin >> d; M.insert(d); }
    M.insert("1"); M.insert("0");
    fin.close();
    ifstream ffin("cod.in");
    ffin >> S;
    n = S.size();
    for(auto e:M)
    {
        cout << e << endl;
    }
    cout << "------------" << endl << S<<endl;

    for (i = 0; i < n; i++) v[i] = i + 1, pred[i] = i - 1;
    for (i = 1; i < n; i++)
    {
        if (M.find(S.substr(0, i + 1)) != M.end())
            v[i] = 1, pred[i] = -1;

    }

    cout << endl << "--------------" << endl;
    for (i = 0; i < n; i++)
        cout << v[i] << " ";

    for (i = 1; i < n; i++)
        for (j = i - 1; j >= 0; j--)
            if (M.find(S.substr(j + 1, i - j)) != M.end())
            {
                v[i] = ((v[i] <= v[j]+1) ? v[i] : v[j] + 1);
                if (v[i] == v[j] + 1) pred[i] = j;
            }

    cout << endl << "--------------" << endl;
    for (i = 0; i < n; i++)
        cout << v[i] << " ";
    cout << endl;
    for (i = 0; i < n; i++)
        cout << pred[i] << " ";

    cout << endl;
    i = n - 1;
    while (i != -1)
        cout << S.substr(pred[i] + 1, i - pred[i]) << "\n", i = pred[i];

    system("pause");


    return 0;
}