Ion este un lingvist pasionat. Recent el a descoperit un text scris într-o limbă necunoscută. Textul este scris pe mai multe linii şi este format din cuvinte scrise cu litere mici din alfabetul latin, separate prin spaţii sau/şi semne de punctuaţie (,:;.!?-). Ion a fost frapat că există multe similitudini între cuvintele din text. Fiind foarte riguros, Ion definește similitudinea a două cuvinte după cum urmează. Fie c1 şi c2 două cuvinte. Cuvântul c1 poate fi obţinut din cuvântul c2 printr-o succesiune de operaţii elementare. Operaţiile elementare ce pot fi folosite sunt:

move(c1, c2) – Mută primul caracter din c1 la sfârşitul cuvântului c2 (de exemplu, dacă c1="alba" şi c2="neagra", după efectuarea operaţiei move(c1, c2), c1 va fi "lba", iar c2 va fi "neagraa")
insert(c1, x) – Inserează caracterul x la începutul lui c1 (de exemplu, dacă c1="alba" şi x='b', după executarea operaţiei insert(c1,x), c1 va fi "balba")
delete(c1) – Şterge primul caracter din c1 (de exemplu, dacă c1="alba", după executarea operaţiei delete(c1), c1 va fi "lba")

Definim similitudinea dintre c1 şi c2 ca fiind numărul minim de operații insert şi delete ce trebuie să fie executate pentru a transforma cuvântul c1 în cuvântul c2 (operațiile move nu se numără).
Fie c0 primul cuvânt din text. Începând cu c0 putem construi lanțuri de k-similitudine.
Un lanţ de k-similitudine este o succesiune de cuvinte distincte din text cu următoarele proprietăți:

dacă cuvântul x apare în lanţ înaintea cuvântului y, atunci prima apariţie a lui x în text precedă prima apariţie a lui y în text;
dacă x şi y sunt cuvinte consecutive în lanţ (în ordinea x y), atunci similitudinea dintre x şi y este mai mică sau egală decât k;
lanţul este maximal (adică nu putem adăuga încă un cuvânt la sfârşitul acestui lanţ, astfel încât să fie respectate proprietăţile precedente).

Cerința

Scrieţi un program care să determine numărul de lanţuri de k-similitudine care încep cu c0.

Date de intrare

Fișierul de intrare lant2.in conţine pe prima linie valoarea k. Pe următoarele linii se află textul dat.

Date de ieșire

Fișierul de ieșire lant2.out va conţine o singură linie pe care va fi scris numărul de lanţuri de k-similitudine care încep cu c0.

Restricții și precizări

Lungimea unei linii din text nu depășește 1000 de caractere.
Lungimea unui cuvânt nu depășește 30 de caractere.
Numărul total de cuvinte distincte este de cel mult 150.
Pentru datele de test, numărul de lanţuri de k-similitudine care încep cu c0 va fi mai mic sau egal cu 2.000.000.000

Exemplu

lant2.in

5
ana are mere, banane,
pere si castane.

lant2.out

Explicație

Lanţurile de 5-similitudine care se pot forma sunt:
ana are mere pere
ana are pere
ana are banane castane
ana are si
ana banane castane
ana si

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema lant2:

#include <fstream>
#include <cstring>
#include <vector>
 
using namespace std;
 
char cuv[160][32];
int n, K; /// n-numarul de cuvinte
vector<int> L[200];
int grad[160]; /// gradele exterioare ale varfurilor
int dp[160];
 
void Citire()
{
    char text[1010], *p;
    char sep[] = " ,:;.!?-";
    bool gasit;
    int i;
    ifstream fin("lant2.in");
    fin >> K;
    fin.get();
    n = 0;
    while (fin.getline(text, 1001))
    {
        //cout << text << "\n";
        p = strtok(text, sep);
        while (p != NULL)
        {
            gasit = false;
            for (i = 1; i <= n && !gasit; ++i)
                if (strcmp(p, cuv[i]) == 0)
                    gasit = true;
            if (!gasit)
            {
                n++;
                strcpy(cuv[n], p);
            }
            p = strtok(NULL, sep);
        }
    }
    fin.close();
}
 
int Lewenshtein(char *p, char *q)
{
    int np, nq, i, j;
    int d[35][35];
    np = strlen(p);
    nq = strlen(q);
    for (i = 0; i <= np; i++)
        d[i][nq] = np - i;
    for (j = 0; j <= nq; j++)
        d[np][j] = nq - j;
    for (i = np - 1; i >= 0; i--)
        for (j = nq - 1; j >= 0; j--)
        {
            d[i][j] = 1 + d[i][j + 1];
            if (d[i][j] > 1 + d[i + 1][j])
                d[i][j] = 1 + d[i + 1][j];
            if (p[i] == q[j] && d[i][j] > d[i + 1][j + 1])
                d[i][j] = d[i + 1][j + 1];
        }
    return d[0][0];
}
 
void ConstrGraf()
{
    int i, j;
    for (i = 1; i < n; ++i)
        for (j = i + 1; j <= n; ++j)
            if (Lewenshtein(cuv[i], cuv[j]) <= K)
            {
                grad[i]++;
                L[i].push_back(j);
            }
}
 
void NrLanturi()
{
    int i, rez, nod;
    unsigned int j;
    dp[1] = 1;
    for (i = 1; i <= n; i++)
        for (j = 0; j < L[i].size(); j++)
        {
            nod = L[i][j];
            dp[nod] += dp[i];
        }
    rez = 0;
    for (i = 1; i <= n; i++)
        if (grad[i] == 0) rez += dp[i];
    ofstream fout("lant2.out");
    fout << rez << "\n";
    fout.close();
}
 
int main()
{
    Citire();
    ConstrGraf();
    NrLanturi();
    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #2191 lant2

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #2191 lant2 de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #2191 lant2