Po serii zagadnień grafowych, na zakończenie cyklu zadań "normalnych" z laboratorium z ASD pojawia się zadanie ze stringologii. Podczas laboratorium prezentujemy dwa różne rozwiązania tego zadania, jedno bardziej teoretyczne i w praktyce mniej efektywne (oparte na metodzie etykietowania), a drugie efektywniejsze, choć obarczone teoretyczną niepewnością wyniku (korzystające z haszowania).
Zadanie LEX (Porównywanie leksykograficzne)
Dostępna pamięć: 64MB.
Niech \( \displaystyle s=s_1s_2\ldots s_n \) będzie \( \displaystyle n \)-literowym słowem złożonym z małych liter alfabetu angielskiego. Będziemy zajmować się podsłowami tego słowa, czyli spójnymi fragmentami postaci \( \displaystyle s[i{\ldotp\ldotp}j]=s_is_{i+1}\ldots s_j \). Naszym celem jest leksykograficzne porównywanie różnych par takich podsłów.
Powiemy, że słowo \( \displaystyle u \) jest mniejsze leksykograficznie (czyli słownikowo) niż słowo \( \displaystyle v \), jeżeli:
- słowo \( \displaystyle u \) jest prefiksem właściwym słowa \( \displaystyle v \), tzn. \( \displaystyle u \) stanowi początkowy fragment \( \displaystyle v \) krótszy niż \( \displaystyle v \), lub
- słowa \( \displaystyle u \) i \( \displaystyle v \) różnią się na jakiejś pozycji i na pierwszej takiej różniącej je pozycji \( \displaystyle u \) zawiera literę mniejszą niż odpowiadająca jej litera w słowie \( \displaystyle v \).
Tę relację zapisujemy jako \( \displaystyle u < v \).
Na przykład, słowo abaab jest (leksykograficznie) mniejsze niż abaababa, słowo abaa jest mniejsze niż ababa, ale ani abab nie jest mniejsze niż abaab, ani słowo abaab nie jest mniejsze od abaab (czyli od siebie samego).
Wejście
W pierwszym wierszu standardowego wejścia znajdują się dwie liczby całkowite \( \displaystyle n \) oraz \( \displaystyle m \) ( \( \displaystyle 1 \le n,m \le 300\,000 \) ), oznaczające długość słowa \( \displaystyle s \) oraz liczbę zapytań. Drugi wiersz zawiera \( \displaystyle n \)-literowe słowo. Każdy z kolejnych \( \displaystyle m \) wierszy zawiera cztery liczby całkowite \( \displaystyle a,b,c,d \) ( \( \displaystyle 1 \le a \le b \le n \), \( \displaystyle 1 \le c \le d \le n \) ), oznaczające zapytanie o porównanie leksykograficzne słów \( \displaystyle s[a{\ldotp\ldotp}b] \) oraz \( \displaystyle s[c{\ldotp\ldotp}d] \).
Wyjście
Na standardowe wyjście Twój program powinien wypisać \( \displaystyle m \) wierszy, z których każdy powinien zawierać jeden znak: '<', '>' lub '=', w zależności od tego, czy pierwsze podsłowo z danego zapytania jest mniejsze czy większe leksykograficznie od drugiego podsłowa, czy też równe temu podsłowu.
Przykład
Dla danych wejściowych:
13 3
abaababaabaab
8 13 7 7
6 11 4 6
3 5 11 13
poprawnym wynikiem jest:
<
>
=
Wyjaśnienie do przykładu: W pierwszym zapytaniu rozważamy podsłowa aabaab oraz b, w drugim - abaaba oraz aba, a w trzecim - aab oraz aab.