Responsive image
Meniu
Toate soluțiile
Soluţii trimise de tine
Compilator online
Ajutor

Lant

Adăugată de :
sorynsoo
Sursă :
OJI2005
Autor :
-
Grupă :
Mare
Punctaj :
0 pc

Restricţii

Citire / Scriere :
stdin, stdout
Limită timp :
100 ms
Limită memorie :
1024 kbytes

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:

 

Operaţia

Efect

Exemplu

move(c1, c2)

Mută primul caracter din c1 la sfârşitul cuvântului c2

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

Dacă c1=”alba” şi x=’b’, după executarea operaţiei insert(c1,x), c1 va fi “balba”.

delete(c1)

Şterge primul caracter din c1

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 £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ţă

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 conţine pe prima linie valoarea k. Pe următoarele linii se află textul dat.

 

Date de ieşire

Fişierul de ieşire 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

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 £150.

Pentru datele de test, numărul de lanţuri de k-similitudine care încep cu c0 va fi £2000000000 (două miliarde).

 

Exemplu

 Date de intrare 

  Date de iesire

  Explicaţie

  5

  ana are mere, banane,

  pere si castane.

  6

  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


Trimite o solutie

Format: cpp şi c

Selectează runda

Trebuie să fii logat pentru a trimite surse


Indicații rezolvare

Siruri de caractere, Programare dinamica


Comentarii

Adauga un comentariu: Click !