Koniec kola: 3. jún 2019 23:59
11 days
Počet bodov:
Popis:  12b
Program:  8b

V krajine, kde sa piesok lial a voda sypala, je jazierko s radom kameňov. Kamene sú v poradí označené písmenami reťazca \(S\) – prvý kameň má písmeno \(S[0]\), druhý \(S[1]\) atď. Na každom kameni je kúsok pizze. Žabiak Žaba je hladný a preto chce preskákať cez čo najviac kameňov. Nie je to ale také jednoduché, pretože na rozdiel od žiab v normálnom svete nemôže skočiť do vody, v sypajúcej vode totiž plávať nevie. Vie sa však po brehu jazera vrátiť zase na začiatok a skákať po kameňoch odznova. Kamene sú naviac príliš malé na to, aby sa na nich otáčal, čiže nemôže skákať na predchádzajúce kamene, je ale dostatočne silný na to, aby doskočil na kameň ľubovoľne ďaleko.

Problém je ešte zapeklitejší, pretože v krajine práve vládne krutovládca s menom \(T\) a ten vydal rozkaz, že ak niekto nebude skákať po kameňoch, ktoré tvoria reťazec \(T\), tak ich roztrhne ako žabu. Keby Žaba nebol prototypom dobrého občana, všetko by bolo jednoduchšie. Preskákal by postupne po každom kameni a dúfal, že si ho nikto nevšimne. To však nie je ochotný spraviť, a preto teraz rozmýšľa, či vie skočiť na každý kameň v jazierku a pritom neporušiť vládcov rozkaz.

Úloha

Máme dva reťazce, \(S\) a \(T\). Z reťazca \(S\) vieme vytvoriť podreťazec tak, že z neho vyškrtneme niektoré písmená a zvyšné zachováme v pôvodnom poradí. Zoberme si všetky podreťazce \(S\), ktoré sú zhodné s \(T\). Zistite, či každý znak reťazca \(S\) patrí aspoň do jedného takéhoto podreťazca.

Formát vstupu

Na prvom riadku vstupu je číslo udávajúce počet testovacích zád. Sád je najviac sto. Nasledujú dva riadky pre každú sadu, na ktorých sú reťazce \(S\) a \(T\). Reťazce pozostávajú z malých písmen anglickej abecedy a nie sú prázdne. Dĺžka každého reťazca nepresiahne \(10^5\) a dĺžka všetkých reťazcov v jednom vstupe nepresiahne \(10^6\).

Formát výstupu

Vypíšte ano, ak sa každý znak reťazca \(S\) nachádza aspoň v jednom z podreťazcov tvoriacich slovo \(T\). Inak vypíšte nie.

Hodnotenie

\(4\) testovacie sady, každá za \(2\) body. Platia v nich nasledovné obmedzenia:

Sada 1 2 3 4
dĺžka každého reťazca \(\leq\) \(100\) \(1\,000\) \(10\,000\) \(100\,000\)

Príklad

Input:

3
haha
ha
zabajezaba
zaba
kamen
ak

Output:

ano
nie
nie

Odovzdávanie

Na odovzdávanie sa musíš prihlásiť

Otázky a diskusia

Po skončení kola budete mať príležitosť na diskutovanie o riešeniach v diskusii pod vzorovým riešením.