Условие
ЗАДАЧА А. НОТИ
---
Пешо Кода е не само отличен програмист, но и автор на музика. Написал е десетки мегафонии (нов вид жанр, създаден от него). Обхванат от актуалната мания всичко да се криптира, той си изработил собствена система за шифриране, за да е сигурен, че никой няма да открадне творбите му. Въпреки това остават съмнения за нерегламентирано използване на творбите му, тъй като често чува фрагменти от тях в ефира. За да провери това, Пешо иска от вас да напишете програма, която проверява дали определени чужди творби съдържат негови фрагменти.
Всяка заявка се състои от два реда, всеки от които е низ шифриращ нотен текст с дължина от 2 до 20 000 000 ноти. На първия ред е шифрирана съмнителната творба, а на втория – Пешовият фрагмент. Правилата за шифриране са следните:
- A, A#, B, C, C#, D, D#, E, F, F#, G, G# описват тоновете през един полутон, съответно: ла, ла диез, си, до, до диез, ре, ре диез, ми, фа, фа диез, сол, сол диез;
- редица от ноти, оградена в скоби, последвана непосредствено от ’x’и цяло десетично число n (≥ 2), означава‚ че поставеното в скоби трябва да се повтори n пъти. Такава последователност може да е част от по-дълга повторена последователност;
- интервалите между елементите на нотацията се поставят за по-лесно четене.
Така например популярната песничка “Мила моя мамо”: Ми Фа Ми Фа Сол Сол Ми Фа Ми Фа Сол Сол Ла Сол Ла Сол Фа Фа Сол Фа Сол Фа Ми Ми може да се запише като EFEFGG EFEFGG AGAGFF GFGFEE или пък като (EFEFGG)x2 AGAGFF GFGFEE.
За всяка заявка, програмата трябва да изведе на стандартния изход броя на позициите, на които Пешовият фрагмент се среща в съмнителната творба. Един фрагмент с дължина K ноти се среща на дадена позиция в изследваната творба, ако поднизът от K последователни ноти, започвайки от тази позиция, съвпада с фрагмента с точност до транспониране. Транспонирането представлява изместване на всяка нота на фрагмента на един и същ брой полутонове нагоре или надолу циклично (като след G# следва A и обратно). Например Ла Ла Фа-диез (A A F#), транспониран с два полутона надолу, става Сол Сол Ми (G G E), поради което можем да кажем, че той се съдържа в песничката „Мила моя мамо“.
Примерен вход:
(EFEFGG)x2 AGAGFF GFGFEE
A A F#
EGEGAGFED DFDFGFEDC EGEGAGFED B AGFEDC
DF
GEE FDD CDEFGGG GEE FDD CEGGCCC
AAA
(D)x5EF (E)x5FG GEE FDD CEGGCCC
CE
((EF)x2GG)x2 (AG)x2FF (GF)x2EE
A G A
Примерен изход:
1
6
3
1
2
« Предходна страница
Решение
Въпрос