Задача D Агітації Перед виборами завжди є період агітації. Pascal програма

Львівська районна учнівська олімпіада з інформатики 2015

Задача D Агітації Перед виборами завжди є період агітації.

Різні партії влаштовують мітинги на площах міст, де постійно скандують гасла. Одного передвиборчого дня Зеник вирішив прогулятися містом. Поки він гуляв центральними вулицями свого рідного міста, то чув, як звідусіль долинали різні гасла. Але він чув тільки кінцівки фраз, тобто, якщо скандували “Слава Україні!”, то Зеник міг почути “…ні”, або “…країні”. На жаль, агітатори не є дуже креативними людьми, і скандують постійно одне і те ж гасло. Проте вони є дуже наполегливими, і скандують це гасло багато разів підряд. Зенику стало цікаво, скільки ж раз вони скандували це гасло. Вам відоме гасло P, яке скандували агітатори. Також, Вам відомий рядок R, який є конкатенацією (з’єднанням) закінчень рядка P — все те, що почув Зеник. Вам потрібно визначити, яку ж найменшу кількість разів треба було повторити гасло P, щоб Зеник почув те, що він почув.

Вхідні дані: Перший рядок містить гасло P, яке скандували агітатори. Другий рядок містить рядок R – те, що почув Зеник. Кожен рядок складається виключно з малих літер латинського алфавіту.

Вихідні дані: Одне ціле число – мінімальна кількість закінчень рядка P, щоб вийшов рядок R. Гарантується, що результат завжди існує, тобто з закінчень рядка P завжди можна скласти рядок R. Обмеження: 1 ≤ |P|, |R| ≤ 100 000

Приклад вводу: glorytoukraine ukraineaineaine

Приклад виводу: 3

Підказка: Гасло було “glorytoukraine”, а Зеник почув “ukraineaineaine” Почути це він міг наступним чином: glorytoukraine glorytoukraine glorytoukraine: ukraine + aine + aine = ukraineaineaine

{ дана задача по тестах дала лише два бали(((((   }

program d;

var slogan, inp : string;
count, position, len : integer;

function isEqual( {inp,} position, {slogan,} len :integer ):boolean;
begin
{writeln(‘Comparing inp[‘,position,’]=’,copy(inp,position,len),
‘ and slogan[‘,len,’]=’,copy(slogan,length(slogan)-len+1,length(slogan)) );}
while (len>0) and (inp[position+len-1] = slogan[len]) do begin
{writeln(‘ ‘,inp[position+len-1],’=’,slogan[len] );}
dec(len);
end;
isEqual := (len=0);
end;

begin

readln(slogan);
readln(inp);
count := 0;
position := 1;

while position < length(inp) do begin
len := length(slogan);

while not isEqual( {inp,} position, {slogan,} len ) do
dec(len);
inc(count);
inc(position, len);
end;

writeln(count);

end.

Comments

comments