Negrimon a găsit într-o culegere această problemă #legendară: peste un şir de caractere de lungime N
, alcătuit din litere mici ale alfabetului englez, se efectuează M
operaţii de următoarele tipuri:
- Se inserează în şir caracterul
x
, pe poziţiap
, după deplasarea cu o poziţie la dreapta a caracterelor situate pe poziţiile mai mari sau egale cup
. Dacă valoareap
este egală cu lungimea şirului,x
este alipit la finalul şirului. - Se răspunde cu
1
dacă secvenţa de litere care începe la poziţiaq1
şi are lungimealg
coincide literă cu literă, cu secvenţa care începe la poziţiaq2
şi are aceeaşi lungimelg
şi se răspunde cu0
în caz contrar. Este posibil ca cele două secvenţe să se suprapună complet sau parţial în şirul din care ele fac parte.
Cerința
Fiind dat un şir de N
litere mici şi o listă de M
operaţii, să se afişeze răspunsurile la operaţiile de tip 2
, respectând ordinea din succesiunea de operaţii date.
Date de intrare
Fișierul de intrare diez.in
conține pe prima linie valorile N
şi M
, separate printr-un spaţiu cu semnificaţia din enunţ. Pe a doua linie se află un şir de N
litere mici ale alfabetului englez iar următoarele M
linii conţin câte o operaţie în unul dintre formatele:
1 p x
– Datele pentru operaţia de tipul1
.2 q1 q2 lg
– Datele pentru operaţia de tipul2
.
Date de ieșire
În fișierul de ieșire diez.out
se vor scrie valori egale cu 0
sau 1
, câte una pe o linie, reprezentând răspunsurile date, în ordine, la operaţiile de tipul 2
existente în fişierul de intrare.
Restricții și precizări
1 ≤ N, M ≤ 250 000
0 ≤ p ≤
lungimea şirului la momentul inserăriix
este literă mică a alfabetului englezq1, q2 ≥ 0
; se garantează că pentru fiecare operaţie de tipul2
existălg
caractere în şir începând atât cu poziţiaq1
cât şi cu poziţiaq2
1 < lg ≤
lungimea şirului la momentul efectuării operaţiei de tipul2
- Numerotarea caracterelor din şir începe de la poziţia
0
Exemplul 1
diez.in
8 6 abcasfas 2 0 5 3 1 3 d 2 4 7 2 1 1 s 1 10 b 2 0 8 3
diez.out
0 1 1
Explicație
Se compară secvenţele abc
şi fas
care sunt diferite → se afişează 0
Caracterul d
este inserat înainte de poziţia 3
şi se obţine şirul abcdasfas
Se compară subşirurile as
şi as
, sunt identice → se afişează 1
Caracterul s
este inserat înainte de poziţia 1
, se obţine şirul asbcdasfas
Caracterul b
este inserat pe poziţia 10
, poziţia este egală cu lungimea şirului, se obţine şirul asbcdasfasb
Se compară subşirurile asb
si asb
, sunt identice → se afişează 1
Exemplu:
diez.in
6 3 atmatm 2 0 2 4 1 6 a 2 0 3 4
diez.out
0 1
Explicație
Se compară subşirurile atma
şi matm
, sunt diferite → se afişează 0
Caracterul a
se alipeşte la final, se obţine şirul atmatma
Se compară subşirurile atma atma
, sunt identice → se afişează 1