To zadanie jest łatwe!

Jak to mówią "Reklama dźwignią handlu!". Skoro tu jesteś, to przemówiła do ciebie nazwa zadania i masz nadzieję, że jest ona prawdziwa. Niestety, reklamy i spoty nie zawsze mówią prawdę i często czujemy się oszukani przez system. Czytając to zastanawiasz się, czy autor jest uczciwy i rzeczywiście umieścił łatwe zadanie, czy tylko chciał, aby ilość odwiedzin tej strony była większa? Przekonaj się sam czytając treść zadania:

Sprawdź, czy istnieje taki podciąg (niekoniecznie spójny) pierwszego ciągu, który jest równoważny drugiemu ciągowi.

 

Wejście

W pierwszym wierszu liczba t określająca ilość zestawów danych, gdzie t < 105.

Każdy zestaw składa się z dwóch ciągów dużych liter języka angielskiego. Każdy ciąg ma co najmniej jeden i maksymalnie 103 znaków.

Wyjście

Dla każdego zestawu wypisz "Tak", jeśli z pierwszego ciągu można wybrać taki podciąg, który jest równy drugiemu ciągowi lub napis "Nie" w przeciwnym wypadku.

Przykład

Wejście:
4
ALGOLIGA GOLA
LATWEZADANIE LATANIE
SSAK KAS
ALAMA ALAMAKOTA

Wyjście:
Tak
Tak
Nie
Nie

Szkic rozwiązania

Wczytujemy ciągi do dwóch tablic $$tab1$$ i $$tab2$$, a następnie określamy ich długości np. wykorzystując funkcję $$strlen$$ z języka C++. Zadanie rozwiązujemy liniowo ustawiając dwa liczniki na pierwsze komórki tablic i powstępujemy według instrukcji:

  1. Przesuwamy licznik w $$tab1$$ do momentu napotkania pierwszej litery z $$tab2$$.
  2. Gdy już znajdziemy taką literę, przesuwamy licznik drugiej tablicy na następny znak i przechodzimy do kroku 1.

Jeśli zatrzymamy się na ostatniej literze w $$tab2$$ i znajdziemy ją w $$tab2$$, oznacza to, że znaleźliśmy szukany podciąg.