Programowanie i algorytmy

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 {tex}tab1{/tex} i {tex}tab2{/tex}, a następnie określamy ich długości np. wykorzystując funkcję {tex}strlen{/tex} 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 {tex}tab1{/tex} do momentu napotkania pierwszej litery z {tex}tab2{/tex}.
  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 {tex}tab2{/tex} i znajdziemy ją w {tex}tab2{/tex}, oznacza to, że znaleźliśmy szukany podciąg.