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

Combcuv

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

Restricţii

Citire / Scriere :
stdin, stdout
Limită timp :
550 ms
Limită memorie :
4096 kbytes

Se consideră un text format numai din litere mici şi N cuvinte formate de asemenea numai din litere mici. Oricare două cuvinte se pot combina prin întrepătrunderea literelor lor, dar fără a schimba ordinea literelor. De exemplu, abc şi xyzt pot obţine prin combinare abcxyzt sau abxcyzt sau xaybczt, dar nu se poate obţine axbczyt, deoarece y trebuia să apară înaintea lui z, aşa cum este iniţial în xyzt.

Cerinţa

Scrieţi un program care să verifice numărul perechilor de cuvinte din cele N date iniţial care obţin prin combinare o subsecvenţă a textului.

 

Date de intrare

Fişierul de intrare conţine pe prima linie textul, pe a doua linie un număr natural N, iar pe următoarele N linii se află câte un cuvânt.

 

Date de iesire

Fişierul de iesire va conţine un singur număr natural reprezentând numărul de perechi de cuvinte care prin combinare obţin o subsecvenţă a textului.

 

Restricţii şi precizări:

  • Textul conţine cel mult 200 de litere mici; textul nu conţine spaţii.
  • Orice cuvânt conţine cel puţin o literă şi cel mult 30
  • 2 <= N <= 100

Exemplu

Date de intrare

Date de iesire

Explicaţii

faacbtbacabb

5

abac

acbta

bt

cb

atcb

2

Textul este faacbtbacabb şi sunt 5 cuvinte.

Combinând perechea de cuvinte (abac, acbta) putem obţine aacbtbaca, care este subsecvenţă a textului.

Combinând perechea de cuvinte (bt, cb) putem obţine cbtb, care este subsecvenţă a textului.

De remarcat că perechea (abac, atcb) nu poate obţine prin combinare subsecvenţa aacbtbac.


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 !