on 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

LANŢ – Descrierea soluţiei

Se citeşte textul şi se memorează cuvintele distincte din text într-un tablou c.
Fie nc numărul de cuvinte distincte determinate. Fiecare cuvânt este numerotat de la 0 la nc-1 (indicii din tabloul c). Observaţi că numerotarea cuvintelor respectă ordinea primei apariţii în text a cuvintelor.
Asociem problemei un graf orientat astfel:
– nodurile grafului sunt cuvintele distincte din text;
– există arc de la nodul i la nodul j (i<j) dacă numărul minim de operaţii insert şi delete necesare pentru a transforma cuvântul c[i] în cuvântul c[j] este k.
Observaţi că graful asociat problemei nu conţine circuite.
Pentru a determina arcele grafului trebuie să rezolvăm următoarea subproblemă:
să se determine numărul minim de operaţii delete şi insert necesare pentru a transforma cuvântul x în cuvântul y.
Rezolvăm această subproblemă prin programare dinamică.
Fie d[i][j]=numărul minimde operaţii insert şi delete necesare pentru a transforma sufixul lui x care începe la poziţia i în sufixul lui y care începe la poziţia j.
Fie n=lungimea cuvântului x şi m=lungimea cuvântului y.
d[n][j]=m-j, pentru orice j=0,m
d[i][m]=n-i, pentru orice i=0,n
d[i][j]=min {d[i+1][j+1], daca p[i]==q[j]; – move
1+d[i][j+1] – insert
1+d[i+1][j] – delete }
Soluţia este d[0][0].
Numărul de lanţuri de k-similitudine este egal cu numărul de drumuri care încep cu nodul 0 şi se termină într-un nod terminal al grafului (nod cu gradul exterior 0).
Să notăm: nr[i]= numărul de lanţuri de k similitudine care încep cu cuvântul i.
Determinăm nr folosind următoarea relaţie de recurenţă:
nr[i]=1, dacă nodul i este terminal
nr[i]=nr[i1]+nr[i2]+…+nr[ik], unde i1, i2, …, ik sunt noduri din graf cu proprietatea că există arc de la i la ij, pentru j=1,k.

include

define InFile “lant.in”

define OutFile “lant.out”

define LgMaxC 31

define NrMaxC 151

typedef char Cuvant[LgMaxC];

Cuvant c[NrMaxC];
/* contine cuvintele distincte din text, in ordinea primei aparitii */

int nc, k;
int a[NrMaxC][NrMaxC];
int d[LgMaxC+1][LgMaxC+1];
long int nr[NrMaxC];
/* nr[i]= numarul de lanturi de k similitudine care incep cu cuvantul i */

void Citire();
void ConstrGraf();
void Numara(int);

void main()
{
int i;
ofstream fout(OutFile);
Citire();
ConstrGraf();
Numara(0);
fout<<nr[0]<<endl;
fout.close();
}

void Adauga_Cuvant(char p) {int i; / for (i=0; p[i]; i++)
if (!(p[i]>=’a’ && p[i]<=’z’)) cout<<“caractere ilegale “<NrMaxC) cout<<“Prea multe cuvinte\n”;
}

void Citire()
{ifstream fin(InFile);
char s[1001], *p;
fin>>k; fin.get();
while (!fin.eof())
{fin.getline(s,1001);
if (fin.good())
{p=strtok(s,” ,.:;?!-“);
while (p)
{Adauga_Cuvant(p);
p=strtok(NULL,” ,.:;?!-“); }
}
}
fin.close();}

int dist (char *p, char *q)
//determina distanta de editare dintre p si q
{
int n, m, i, j;
/*
d[i][j]=distanta de editare de la cuvantul p+i la cuvantul q+j
fie n= strlen(p) si m=strlen(q);
d[n][j]=m-j, pentru orice j=0,m
d[i][m]=n-i, pentru orice i=0,n
d[i][j]=min {d[i+1][j+1], daca p[i]==q[j]; – move
1+d[i][j+1] – insert
1+d[i+1][j] – delete }
Solutia este d[0][0] */
n=strlen(p); m=strlen(q);
for (i=0; i<=n; i++) d[i][m]=n-i; for (j=0; j<=m; j++) d[n][j]=m-j; for (i=n-1; i>=0; i–)
for (j=m-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=0; i<nc; i++)
{a[i]=(int *) malloc(sizeof(int));
a[i][0]=0;}
for (i=0; i<nc; i++)
for (j=i+1; j<nc; j++)
if (dist(c[i],c[j])<=k)
{
a[i][0]++;
a[i]=(int *)realloc(a[i],(a[i][0]+1)sizeof(int)); a[i][a[i][0]]=j; } }/

void ConstrGraf()
{int i, j;
for (i=0; i<nc; i++)
for (j=i+1; j<nc; j++)
if (dist(c[i],c[j])<=k)
{
a[i][0]++;
a[i][a[i][0]]=j;
}
}

void Numara(int vf)
{
int i;
if (!a[vf][0]) {nr[vf]=1; return;}
long int s=0;
for (i=1; i<=a[vf][0]; i++)
{
if (nr[a[vf][i]]==0)
Numara(a[vf][i]);
s+=nr[a[vf][i]];
// if (s<0) cout<<“Prea multe lanturi\n”;
}
nr[vf]=s;
}