Runda 5: Koledzy z klasy

24.06.2009

Organizatorzy pewnego konkursu informatycznego zaprosili do udziału uczniów różnych klas. Po kilku dniach konkursu okazało się, że rozwiązania uczniów z tych samych klas są bardzo podobne. Organizatorzy bardzo się ucieszyli i postanowili odtworzyć podział na klasy na podstawie podobnieństw między rozwiązaniami uczestników. Jednak ponieważ rozwiązań jest bardzo, bardzo wiele, proces ten trzeba zautomatyzować. Potrzebny jest zatem program, który mając dane dwa rozwiązania będzie porównywał ich fragmenty, informując organizatorów, czy są one identyczne, czy nie.

Wejście

W pierwszych dwóch liniach wejścia znajdują się dwa ciągi znakowe, każdy nie dłuższy niż 200 000 znaków, składające się z małych i wielkich liter alfabetu angielskiego oraz cyfr - są to dwa porównywane rozwiązania uczestników. Następnie na wejściu znajduje się conajwyżej 500 000 zapytań. Każde z nich jest opisane trzema liczbami a, b, n, które oznaczają kolejno: początek fragmentu w rozwiązaniu pierwszym, początek fragmentu w rozwiązaniu drugim oraz długość obu fragmentów. Organizatorzy zauważyli, że oba fragmenty muszą mieć taką samą długość - w przeciwnym wypadku nie mogłyby być identyczne! Wejście kończy się zapytaniem 0 0 0

Wyjście

Dla każdego zapytania należy wypisać jedno słowo: TAK jeżeli fragment rozwiązania pierwszego rozpoczynający się na a-tej literze i mający długość n jest identyczny z fragmentem rozwiązania drugiego rozpoczynającego się na b-tej literze i mającego długość n, lub NIE w przeciwnym wypadku. Pierwsza litera każdego rozwiązania ma numer 1.

Przykład

Dla danych wejściowych

LoremipsumdolorsitametconsecteturadipiscingelitIntegernonmaurissed
SedmipurusrhoncussedconvalliseuplaceratataugueDuisjustocrasamet
5 4 3
5 4 4
23 21 3
19 60 4
0 0 0

poprawną odpowiedzią jest

TAK
NIE
TAK
TAK

kod: CLASSMATES, limity: 9 s, 64 MB

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com