Virkņu pagarināšana

ID: pagarin
Grūtība: 3/5
Laika limits: 1

Uzdevums

Ir divas simbolu virknes - A un B, kas katra sastāv no angļu alfabēta mazajiem burtiem.

Kādas simbolu virknes X pagarināšana notiek, iespraužot tajā patvaļīgu skaitu (0 vai vairāk)pasvītrojuma simbolu jebkurā tās vietā (sākumā, beigās vai pa vidu). Ja virkne X ir 'abcbcd', tad tai atbilstošās pagarinātās virknes ir, piemēram, 'abcb_cd', '_a_bcbcd_' un 'abcb_cd_'.

Ja A1 ir virknes A pagarinātā virkne, bet B1 ir virknes B pagarinātā virkne un virknes A1 un B1 ir vienāda garuma, tad var aprēķināt attālumu starp šīm virknēm kā attālumu starp šo virkņu atbilstošajiem simboliem summu. Attālums starp diviem burtiem ir šo burtu ASCII kodu starpības absolūtā vērtība. Attālums starp burtu un pasvītrojuma zīmi ir dots naturāls skaitlis (šis skaitlis ir viens un tas pats visiem burtiem).

Uzrakstiet programmu, kas dotām virknēm A un B atrod mazāko iespējamo attālumu starp šo virkņu pagarinātajām virknēm A1 un B1!

 

Ievaddati

Teksta fails pagarin.dat sastāv no trim rindām - pirmajā rindā dota virknes A, otrajā - virknes B vērtība, bet trešajā naturāla skaitļa K (attālums no pasvītrojuma zīmes līdz burtam, 1≤K≤100) vērtība. Virkņu A un B garums nepārsniedz 2000 burtus.

 

Izvaddati

Teksta faila pagarin.rez vienīgajā rindā jāizvada vesels skaitlis - mazākais iespējamais attālums starp A1 un B1.

 

Piemērs

pagarin.datpagarin.rez
cmc
snmn
2
10
  
pagarin.datpagarin.rez
koiv
ua
1
5
  
pagarin.datpagarin.rez
mj
jao
4
12

 

Atsauces

Uzdevums izmantots Horvātijas informātikas olimpiādē 2002.gadā
© 2001-2002 olimps! http://www.lio.lv/olimps/