Ajuntant dues paraules P35251


Statement
 

pdf   zip

thehtml

Donades dues paraules formades amb lletres minúscules, heu de calcular quantes paraules es poden formar amb totes les lletres, tot respectant l’ordre relatiu de les lletres dintre de cada paraula. Les paraules formades no poden tenir lletres adjacents iguals.

Entrada

L’entrada consisteix en diversos casos. Les paraules tenen entre 1 i 1000 lletres minúscules.

Sortida

Per a cada cas, escriviu la quantitat de paraules possibles. Com que el resultat pot ser molt gros, feu els càlculs mòdul 108 + 7.

Si us fixeu en el primer exemple, es poden comptar paraules repetides. Si ens imaginem que la segona paraula és ab, les paraules podrien ser abab i abab.

Pista

Siguin n i m les mides de les dues paraules, respectivament. La solució esperada és una programació dinàmica amb uns 2 n m estats.

Public test cases

  • Input

    ab ab
a b
z z
ae z
abc def
abba bababa
abcdefghij klmnopqrst
abcdefghijklmnopqr abcdefghijklmnopqr

    Output

    2
2
0
3
20
6
184756
17558187
    • Information
    Author
    Salvador Roura
    Language
    Catalan
    Official solutions
    C++
    User solutions
    C++